[Dynamic Programming I] By TonyFang

[Problem 1] The Bigest square (square.c/pas/cpp)

There is a n * m square which contains only 0 and 1, Please try to find a bigest square which isn't including 0, and output the side of the bigest sqaure.

[Sample Input]

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

[Sample Output]

2

[Code]

//square.cpp   (AC 15ms, 1Mb)
/*
 * CodeForces Problem The Biggest Square
 * Code By TonyFang
 * Mail To tony-fang@foxmail.com
 * Copyright TonyFang (in CodeForces) 2013
 * All rights reserved.
 * Copyright TonyFang 2000-2013 (now)
 * All rights reserved.
 */
# include <iostream>
# include <stdio.h>
# include <string.h>
# define MAX 110
using namespace std;
int main() {
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	int n, m, dp[MAX][MAX], map[MAX][MAX];
	int Line[MAX][MAX], Row[MAX][MAX], ans = -1;
	memset(map,0,sizeof(map));
	memset(Line,0,sizeof(Line));
	memset(Row,0,sizeof(Row));
	memset(dp,0,sizeof(dp));
	scanf("%d %d",&n,&m);
	for (int i = 1;i <= n;i ++)
		for (int j = 1;j <= m;j ++) {
			scanf("%d",&map[i][j]);
			if (map[i][j]) {
				Line[i][j] = Line[i-1][j] + 1;
				Row[i][j] = Row[i][j-1] + 1;
			}
		}
	for (int i = 1;i <= n;i ++)
		for (int j = 1;j <= m;j ++) {
			if(map[i][j]) {
				dp[i][j] = 1;
				if (Line[i][j] - 1 >= dp[i-1][j-1] && Row[i][j] - 1 >= dp[i-1][j-1])
						dp[i][j] = dp[i-1][j-1] + 1;
				}
				if (dp[i][j] > ans) ans = dp[i][j];
			}
	printf("%d\n",ans);
	return 0;
}