1057: [ZJOI2007] 棋盘制作
- Time Limit: 20 Sec Memory Limit: 162 MB
- Submit: 3917 Solved: 2046
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=1057 ]
- Description
国际象棋是世界上最古老的博弈游戏之一, 和中国的围棋, 象棋以及日本的将棋同享盛名. 据说国际象棋起源
于易经的思想, 棋盘是一个 8*8 大小的黑白相间的方阵, 对应八八六十四卦, 黑白对应阴阳. 而我们的主人公小 Q,
正是国际象棋的狂热爱好者. 作为一个顶尖高手, 他已不满足于普通的棋盘与规则, 于是他跟他的好朋友小 W 决定
将棋盘扩大以适应他们的新规则. 小 Q 找到了一张由 N*M 个正方形的格子组成的矩形纸片, 每个格子被涂有黑白两种
颜色之一. 小 Q 想在这种纸中裁减一部分作为新棋盘, 当然, 他希望这个棋盘尽可能的大. 不过小 Q 还没有决定是找
一个正方形的棋盘还是一个矩形的棋盘 (当然, 不管哪种, 棋盘必须都黑白相间, 即相邻的格子不同色), 所以他
希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积, 从而决定哪个更好一些. 于是小 Q 找到了即将参加全
国信息学竞赛的你, 你能帮助他么?
Input
第一行包含两个整数 N 和 M, 分别表示矩形纸片的长和宽. 接下来的 N 行包含一个 N * M 的 01 矩阵, 表示这张矩形
纸片的颜色 (0 表示白色, 1 表示黑色).
Output
包含两行, 每行包含一个整数. 第一行为可以找到的最大正方形棋盘的面积, 第二行为可以找到的最大矩形棋
盘的面积 (注意正方形和矩形是可以相交或者包含的).
- Sample Input
- 3 3
- 1 0 1
- 0 1 0
- 1 0 0
- Sample Output
- 4
- 6
- HINT
N, M ≤ 2000
Source
复杂度: O(n * m)
- #include <iostream>
- #include <fstream>
- #include <sstream>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <string>
- #include <cstring>
- #include <algorithm>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <set>
- #include <map>
- #include <list>
- #include <iomanip>
- #include <cctype>
- #include <cassert>
- #include <bitset>
- #include <ctime>
- using namespace std;
- #define pau system("pause")
- #define ll long long
- #define pii pair<int, int>
- #define pb push_back
- #define pli pair<ll, int>
- #define pil pair<int, ll>
- #define clr(a, x) memset(a, x, sizeof(a))
- const double pi = acos(-1.0);
- const int INF = 0x3f3f3f3f;
- const int MOD = 1e9 + 7;
- const double EPS = 1e-9;
- /*
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- #define TREE tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update>
- TREE T;
- */
- int n, m, mmp[2015][2015], ans1, ans2;
- int h[2015][2015], l[2015][2015], r[2015][2015];
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- scanf("%d", &mmp[i][j]);
- }
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- if (j> 1 && mmp[i][j - 1] != mmp[i][j]) {
- l[i][j] = l[i][j - 1];
- r[i][j] = r[i][j - 1];
- } else {
- l[i][j] = j;
- int k;
- for (k = j + 1; k <= m; ++k) {
- if (mmp[i][k] == mmp[i][k - 1]) break;
- }
- r[i][j] = k - 1;
- }
- }
- for (int j = 1; j <= m; ++j) {
- if (i> 1 && mmp[i - 1][j] != mmp[i][j]) {
- h[i][j] = h[i - 1][j] + 1;
- l[i][j] = max(l[i][j], l[i - 1][j]);
- r[i][j] = min(r[i][j], r[i - 1][j]);
- } else {
- h[i][j] = 1;
- }
- ans2 = max(ans2, h[i][j] * (r[i][j] - l[i][j] + 1));
- int d = min(h[i][j], r[i][j] - l[i][j] + 1);
- ans1 = max(ans1, d * d);
- }
- }
- printf("%d\n%d\n", ans1, ans2);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2944754.html