UVa 10074

From Algorithmist
Jump to navigation Jump to search

10074 - Take the Land[edit]

Summary[edit]

A Dynamic Programming problem. (Same with 108 and 10667)

Explanation[edit]

Create matrix A[m][n],where A[i][k]- longest line containing no 1 starting from (i,k). For all (i,k) do l-width j-height

	for (kk=i,l=1,j=matrix[i][k];kk<m;kk++,l++)
	 if (matrix[kk][k])
	 {
		if (j>matrix[kk][k]) j=matrix[kk][k];
		if (j*l>max) max=j*l;
	 }else break;

Implementations[edit]

//Created by Zaspire
#include <stdio.h>

int m,n,matrix[100][100];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	int i,k,j,kk,l,max;
	while (scanf("%d %d",&m,&n),m!=0||n!=0)
	{
		max=0;
		for (i=0;i<m;i++)
			for (k=0;k<n;k++)
			{
				scanf("%d",&j);
				matrix[i][k]=j;
			}
		for (j=0;j<m;j++)
		{
			k=0;
			for (i=n-1;i>=0;i--)
			{
				if (matrix[j][i]==0) k++;
				else k=0;
				matrix[j][i]=k;
			}
		}
		for (i=0;i<m;i++)
			for (k=0;k<n;k++)
				if (matrix[i][k])
				{
					j=matrix[i][k];
					if (j>max) max=j;
					for (kk=i+1,l=2;kk<m;kk++,l++)
						if (matrix[kk][k])
						{
							if (j>matrix[kk][k]) j=matrix[kk][k];
							if (j*l>max) max=j*l;
						}else break;
				}
		printf("%d\n",max);
	}
	return 0;
}

Input[edit]

6 7
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 1 0 1 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
6 7
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 1 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
0 0

Output[edit]

6
8

References[edit]