广场问题 - 无幻の编程 - 对于一个初学者来说,野心也是必须的...
广场问题
问题描述:
现城市规划，要建广场，广场必须是正方形。但建设广场的那片区域，有一些古树、清泉不能被破坏。地图上可用来建设广场的地方标0，有古树和清泉的地方标1，整个地图就是一个1、0矩阵，现在把确定建设广场地址的任务交给了你，希望你能计算出广场到底能建多大。
输入
输入包含多组测试数据，每组测试数据的第一行是两个正整数M、N（1<=M<=300，1<=N<=300），表示建设广场的矩形区域的长和宽。然后接下来是M×N的0、1矩阵。输入数据以0 0结束。
输出
对应每组测试数据，仅输出一行，即广场的最大边长。
样例输入
3 4
0 1 0 0
0 0 0 0
1 0 0 1
5 5
0 0 0 1 0
0 0 0 0 0
1 1 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0
样例输出
2
3
#include <iostream>
#include <fstream>
using namespace std;
const int N=100;
int main()
{
int length,width;
int lengthCount=0;
int widthCout=0;
int area[N][N];
int square[N][N];
ifstream cin1("inputtest3.dat");
while(!cin1.eof())
{
cin1>>length>>width;
if (length==0 || width==0)
{
break;
}
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
cin1>>area[i][j];
}
}
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
if (area[i][j]==0)
{
lengthCount=0;
widthCout=0;
int times=1;
for(int p=j;p<width;p++)
{
if (area[i][p]!=0)
{
lengthCount=p-j;
break;
}
else
{
lengthCount++;
}
}
for (int q=i;q<length;q++)
{
if (area[q][j]!=0)
{
widthCout=q-i;
break;
}
else
{
widthCout++;
}
}
if (lengthCount>widthCout)
{
lengthCount=widthCout;
}
else
{
widthCout=lengthCount;
}
while(1 && lengthCount>1)
{
for (int k=j+times;k<j+lengthCount;k++)
{
if (area[i+times][k]!=0)
{
lengthCount=k-j;
break;
}
}
for (int l=i+times;l<i+widthCout;l++)
{
if (area[l][j+times]!=0)
{
widthCout=l-i;
break;
}
}
if (lengthCount>widthCout)
{
lengthCount=widthCout;
}
else
{
widthCout=lengthCount;
}
times++;
if (times>=lengthCount)
{
break;
}
}
square[i][j]=lengthCount;
}
else
square[i][j]=0;
}
}
int maxSquare=0;
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
maxSquare=max(maxSquare,square[i][j]);
}
}
cout<<maxSquare<<endl;
}
return 0;
}
#include <fstream>
using namespace std;
const int N=100;
int main()
{
int length,width;
int lengthCount=0;
int widthCout=0;
int area[N][N];
int square[N][N];
ifstream cin1("inputtest3.dat");
while(!cin1.eof())
{
cin1>>length>>width;
if (length==0 || width==0)
{
break;
}
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
cin1>>area[i][j];
}
}
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
if (area[i][j]==0)
{
lengthCount=0;
widthCout=0;
int times=1;
for(int p=j;p<width;p++)
{
if (area[i][p]!=0)
{
lengthCount=p-j;
break;
}
else
{
lengthCount++;
}
}
for (int q=i;q<length;q++)
{
if (area[q][j]!=0)
{
widthCout=q-i;
break;
}
else
{
widthCout++;
}
}
if (lengthCount>widthCout)
{
lengthCount=widthCout;
}
else
{
widthCout=lengthCount;
}
while(1 && lengthCount>1)
{
for (int k=j+times;k<j+lengthCount;k++)
{
if (area[i+times][k]!=0)
{
lengthCount=k-j;
break;
}
}
for (int l=i+times;l<i+widthCout;l++)
{
if (area[l][j+times]!=0)
{
widthCout=l-i;
break;
}
}
if (lengthCount>widthCout)
{
lengthCount=widthCout;
}
else
{
widthCout=lengthCount;
}
times++;
if (times>=lengthCount)
{
break;
}
}
square[i][j]=lengthCount;
}
else
square[i][j]=0;
}
}
int maxSquare=0;
for (int i=0;i<length;i++)
{
for (int j=0;j<width;j++)
{
maxSquare=max(maxSquare,square[i][j]);
}
}
cout<<maxSquare<<endl;
}
return 0;
}
评论 (0)