Question

一道ACM的练习题，简单，但我找不出错在哪里

题目链接地址：http://par.bianchengla.com/problem/1002
程序如下（无法通过，提交后系统提示结果错误）：
#include <iostream>

using namespace std;

int main(void)
{
int m,n,i,j,len,x,y,z;
bool* data=new bool[3000*3000];
do
{
cin>>m>>n;
if(m<0 || m>3000 || n<0 || n>3000)return -1;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>data[i*n+j];
}
}

len=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(data[i*n+j]==1)continue;
for(x=j+1;x<n;x++)
{
if(data[i*n+x]==1)break;
}

for(y=i+1;y<m;y++)
{
if(data[y*n+j]==1)break;
}

z=(x-j-1)>(y-i-1)?(y-i):(x-j);
if(len<z)len=z;
}
}
cout<<len<<endl;
}while(m!=0 || n!=0);

return 0;
}

Answer 1

因为你在main函数里面开的数组太大了。
很慧友多online judge 都不允许这样的操作。所以你要把bool* data=new bool[3000*3000];作为全局变伏液量。即把它放在main函数的上面。最后可别忘记delete [] data;
还有你程序中的输出操作有点问题。因为题目要求最后是 所有结果一起输出的。而你写的代码是每次输入完一组数据就直接输出结果了。
我知识有限，也只前厅槐能看出这点问题了，希望我的答案对你有所帮助，谢谢。

Answer 2

看来楼上的不是很懂OJ啊. 一组一组输出是没有问题的...

你的算法有问题啊... 需要的是方形的空地... 而不是方形的边框啊~

就算橘清是方形的边框... 你也只检验了两条边... = =||

附一个正确的代码 (算法是DP)

#include <iostream>
using namespace std;

struct node
{
int rl;
int dl;
int available;
int maximun;
};

int main()
{
int m,n;
node** data;
while(true)
{
int result = 0;
cin >> m >> n;
if(m==0 || n==0) break;
data = new node*[m];
for(int i=0;i<m;i++)
{
data[i] = new node[n];
for(int j=0;j<n;j++)
{
cin >>圆哗前芦链 data[i][j].available;
}
}
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=0;j--)
{
if(data[i][j].available == 1)
{
data[i][j].rl = 0;
data[i][j].dl = 0;
data[i][j].maximun = 0;
continue;
}
if(i==m-1)
data[i][j].dl = 1;
else
data[i][j].dl = data[i+1][j].dl + 1;
if(j==n-1)
data[i][j].rl = 1;
else
data[i][j].rl = data[i][j+1].rl + 1;
if(i==m-1 || j==n-1)
data[i][j].maximun = 1;
else
data[i][j].maximun = min(min(data[i][j].dl,data[i][j].rl),data[i+1][j+1].maximun+1);
if(result < data[i][j].maximun) result = data[i][j].maximun;
}
}
cout << result << endl;
for(int i=0;i<m;i++)
{
delete[] data[i];
}
delete[] data;
}
return 0;
}