3068083_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

char array[2001][2001];
int w[2001][2001], h[2001][2001];
int m, n;

int min(int a,int b)
{
	return a < b ? a : b;
}

int main()
{
	int i, j, t;

	while (scanf("%d%d",&m,&n)==2)
	{
		for (i = 0; i < m; i++)
		{
			for (j = 0; j < n; j++)
			{
				scanf("%d",&t);
				array[i][j] = '0'+t;
			}
		}
		for (i = 0; i < n; i++)
		{
			if (array[0][i]=='0')
			{
				h[0][i] = 0;
				w[0][i] = 0;
			}
			else
			{
				if (i==0)
				{
					w[0][i] = h[0][i] = 1;
				}
				else
				{
					h[0][i] = 1;
					w[0][i] = w[0][i-1]+1;
				}
			}
		}
		for (i = 1; i < m; i++)
		{
			if (array[i][0]=='0')
			{
				w[i][0] = 0;
				h[i][0] = 0;
			}
			else
			{
				if (i==0)
				{
					h[i][0] = w[i][0] = 1;
				}
				else
				{
					w[i][0] = 1;
					h[i][0] = h[i-1][0]+1;
				}
			}
		}
		for (i = 1; i < m; i++)
		{
			for (j = 1; j < n; j++)
			{
				if (array[i][j]=='0')
				{
					w[i][j] = h[i][j] = 0;
				}
				else
				{
					if (h[i-1][j]==0)
					{
						h[i][j] = 1;
						w[i][j] = w[i][j-1]+1;
						continue;
					}
					if (w[i][j-1]==0)
					{
						w[i][j] = 1;
						h[i][j] = h[i-1][j]+1;
						continue;
					}
					int w1, h1, w2, h2;
					w1 = w[i][j-1]+1;
					h1 = min(h[i][j-1],h[i-1][j]+1);
					h2 = h[i-1][j]+1;
					w2 = min(w[i-1][j],w[i][j-1]+1);
					if (w1*h1<w2*h2)
					{
						w[i][j] = w2;
						h[i][j] = h2;
					}
					else
					{
						w[i][j] = w1;
						h[i][j] = h1;
					}
				}
			}
		}
		int ans = -1;
		for (i = 0; i < m; i++)
		{
			for (j = 0; j < n; j++)
			{
				t = w[i][j]*h[i][j];
				if (t>ans)
				{
					ans = t;
				}
			}
			printf("\n");
		}
		printf("%d\n",ans);
	}
	return 0;
}