首页 > 代码库 > CSU 1424 Qz’s Maximum All One Square
CSU 1424 Qz’s Maximum All One Square
Description
YH gave Qz an odd matrix consists of one or zero. He asked Qz to find a square that has the largest area. The problem is not so easy, that means the square you find must not contain any zero. Your task is finding the square and you only need to output the area of the matrix. If you help Qz, he will thanks you a lot and treat you a meal. Please call him after the contest if you solve this problem. His number is XXXXXXXXXXXX. Hehe~
Input
For each case, Qz first give you 2 number n and m (1 <= n <= 1000, 1 <= m <= 1000),the matrix is in size of n columns and m rows.
Then Qz will give you the matrix. To avoid cost his money, Qz decided to make this problem a little difficult... Do not worry, he just gave you multiple cases.
Output
For each test case, output the desired answer.
Sample Input
2 2 1 1 1 1 4 4 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1
Sample Output
4 4
这是道很老的题,各大题库基本都有,以前也做过类似的题目。可能是这几天为了私事花了很多心思,做题的时候总是不在状态。
DP应该是一眼就能看出来的,状态转移方程也很简单,需要注意的一点是行号和列号的标示,尤其是在还没有十分清晰明确的思路时,我经常写着写着就搞混了。
#include<stdio.h> #define maxn 1010 int sum[maxn][maxn]; int main() { int m,n,t; while(~scanf("%d%d",&n,&m)) { int i,j,k,ans; for(i = 1;i <= m;i++) { for(j = 1;j <= n;j++) { scanf("%d",&k); sum[i][j] = k + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];//求(i,j)到(1,1)这个点的1的个数。 } } ans = 0; for(i = 1;i <= m;i++) for(j = 1;j <= n;j++) { t = ans;//每次从边长等于ans开始找(剪枝,) int x,y; for(x= i - ans,y = j - ans ; x && y ; x--,y--) { if(x <= 0 || y <= 0) break; int temp1 = sum[i][j] - sum[i][y-1] - sum[x-1][j] + sum[x-1][y-1]; if(temp1 == (t + 1) * (t + 1)) { t++; } else break; } if(t > ans) ans = t; } printf("%d\n",ans * ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。