首页 > 代码库 > 洛谷P1681 最大正方形II
洛谷P1681 最大正方形II
P1681 最大正方形II
题目背景
忙完了学校的事,v神终于可以做他的“正事”:陪女朋友散步。一天,他和女朋友走着走着,不知不觉就来到 了一个千里无烟的地方。v神正要往回走,如发现了一块牌子,牌子上有有一行小字和一张图,小字说道:“找到图上最大的交错正方形之后和我联系,这块地就是 你的了。”在房价疯长的年代,v神当然不愿错过这个机会,于是开始找了起来……以v神的能力当然找不出来了,你能帮v神找出来吗?
题目描述
图上有一个矩阵,由N*M个格子组成,这些格子由两种颜色构成,黑色和白色。请找到面积最大的且内部是黑白交错(即两个相连的正方形颜色不能相同)的正方形。
输入输出格式
输入格式:第一行两个整数N和M,分别表示行数和列数。接下来有N行,每行M个数,0或1分别表示这个格子是黑色或白色。
输出格式:仅有一行,表示满足条件最大正方形的 边长
输入输出样例
输入样例#1:
3 30 1 01 0 01 1 1
输出样例#1:
2
说明
样例解释:
(1,1)到(2,2)这个正方形是满足条件的,它的边长是2
数据范围约定:
对于30%的数据,N <= 20
对于60%的数据,N <=300
对于100%的数据,N <= 1500
【状态】
dp[i][j]表示以(i,j)为右下角的正方形的最大边长
【转移】
若(i,j)与周围四个格子交错,则dp[i][j] = min{dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]} + 1;
否则dp[i][j] = 1
【初始状态】
dp[1][j] = dp[i][1] = 1
【答案】
ans = max{dp[i][j]}
Code
1 #include <bits/stdc++.h> 2 3 inline void read(int &x) 4 { 5 x = 0;char ch = getchar();char c = ch; 6 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 7 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); 8 if(c == ‘-‘)x = -x; 9 }10 inline int min(int a, int b){return a > b ? b : a;}11 inline int max(int a, int b){return a > b ? a : b;}12 13 const int INF = 0x3f3f3f3f;14 const int MAXN = 1500 + 10;15 const int MAXM = 1500 + 10;16 17 int n,m,num[MAXN][MAXM],dp[MAXN][MAXM],ans;18 19 int main()20 {21 read(n);read(m);22 for(int i = 1;i <= n;++ i)23 {24 dp[i][1] = 1;25 for(int j = 1;j <= m;++ j)26 {27 dp[i][j] = 1;28 read(num[i][j]);29 }30 }31 ans = 1;32 for(int i = 2;i <= n;++ i)33 for(int j = 2;j <= n;++ j)34 if((num[i - 1][j - 1] == num[i][j] && num[i - 1][j] == num[i][j - 1]) && num[i - 1][j] != num[i - 1][j - 1])35 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1,ans = max(ans, dp[i][j]);36 else37 dp[i][j] = 1; 38 printf("%d", ans);39 return 0;40 }
洛谷P1681 最大正方形II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。