noj 1020 最大正方形.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

//作者：yesrush
//NOJ 1020 最大正方形
//类似于求最大零矩阵，本程序是在这个程序上略作修改得到
/*

输入：
6
0 0 0 0 0 -1
0 0 0 0 0 -1
-1 -1 -1 0 0 0
-1 0 0 0 0 0
-1 0 0 0 0 0
0 0 -1 0 0 0

输出：
3
*/

#define NMAX 502
int ju[NMAX][NMAX];
int high[NMAX][NMAX];
int l[NMAX][NMAX];
//l[i][j]，第i行以第j列为基准，只要高度小于基准，就向左延伸，最后延伸到的列数
int r[NMAX][NMAX];
//l[i][j]，第i行以第j列为基准，只要高度小于基准，就向右延伸，最后延伸到的列数
int cc[NMAX][NMAX];

int cal(int num)
{
	int i,j,k,min=0,c1,c2;
	//c1，是在第i行包含第j列的全零序列的最左列数
	//c2，是在第i行包含第j列的全零序列的最右列数
	for(i=0;i<=num;i++) high[0][i]=0;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{	//计算零列高度
			if(ju[i][j]==-1) high[i][j]=0;
			else if(ju[i-1][j]==0) high[i][j]=high[i-1][j]+1;
			else high[i][j]=1;
		}
	}
	for(j=0;j<=num;j++)
	{	//初始化第0行的l[][],r[][]值
		l[0][j]=1;
		r[0][j]=num;
	}
	for(i=1;i<=num;i++)
	{
		//计算l[][],r[][]值
		j=1;c1=1;
		while(j<=num)
		{
			while(ju[i][j]==-1)
			{
				l[i][j]=1;//高度为0，可知其向左能延伸到第1列
				j++;
				c1=j;//这个c1显然不合法，修改
			}
			//l[i][j]取l[i-1][j]和c1间的最大值
			if(l[i-1][j]>c1) l[i][j]=l[i-1][j];
			else l[i][j]=c1;
			j++;
		}
		c2=num;k=num;
		while(k>=1)
		{
			while(ju[i][k]==-1)
			{
				r[i][k]=num;//高度为0，可知其向右延伸到第num列
				k--;
				c2=k;//这个c2显然不合法，修改
			}
			//r[i][j]取r[i-1][j]和c2间的最小值
			if(r[i-1][k]>c2) r[i][k]=c2;
			else r[i][k]=r[i-1][k];
			k--;
		}
		//max{high[i][j]*(r[i][j]-l[i][j]+1)&&ju[i][j]==0},为所求答案
		for(j=1;j<=num;j++) 
		{
			cc[i][j]=r[i][j]-l[i][j]+1;//cc为宽
			//不管是宽还是高，都是取二者的最小值，否则求出的最大边长就不是正方形的边长了
			if(cc[i][j]>high[i][j]) cc[i][j]=high[i][j];
			else high[i][j]=cc[i][j];
		}
		for(j=1;j<=num;j++)
		if(min<high[i][j]&&ju[i][j]==0) min=high[i][j];
	}
	return min;
}

int main()
{
	int num,i,j;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
		{
			for(j=1;j<=num;j++)
			scanf("%d",&ju[i][j]);
		}
		cout<<cal(num)<<endl;
	}
	return 0;
}
/*
void printh(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<high[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

void printcc(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<cc[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

void printr(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<r[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}
*/