jzdywf @ 2019-10-08 22:54:16
#include<bits/stdc++.h>
using namespace std;
int m,n;
int ans=1;
int a[3000][3000];
bool b[3000][3000];
void search(int x,int y){
int cnt=1;
bool flag=0;
int i=x,j=y;
while(i!=m&&j!=n){
i++,j++;
for(int p=x;p<=i;p++){
for(int q=y;q<=j;q++){
if(i-p!=j-q&&a[p][q]==1){
flag=1;
break;
}
if(i-p==j-q&&a[p][q]!=1){
flag=1;
break;
}
}
if(flag){
break;
}
}
if(flag){
break;
}
cnt++;
b[i][j]=1;
}
ans=max(ans,cnt);
cnt=1;
flag=0;
i=x,j=y;
while(i!=1&&j!=1){
i--,j--;
for(int p=i;p<=x;p++){
for(int q=j;q<=y;q++){
if(p-i!=q-j&&a[p][q]==1){
flag=1;
break;
}
if(p-i==q-j&&a[p][1]!=1){
flag=1;
break;
}
}
if(flag){
break;
}
}
if(flag){
break;
}
cnt++;
b[i][j]=1;
}
ans=max(ans,cnt);
cnt=1;
flag=0;
i=x,j=y;
while(i!=1&&j!=n){
i--,j++;
for(int p=i;p<=x;p++){
for(int q=y;q<=j;q++){
if(p-i!=j-q&&a[p][q]==1){
flag=1;
break;
}
if(p-i==j-q&&a[p][q]!=1){
flag=1;
break;
}
}
if(flag){
break;
}
}
if(flag){
break;
}
cnt++;
b[i][j]=1;
}
ans=max(ans,cnt);
cnt=1;
flag=0;
i=x,j=y;
while(i!=m&&j!=1){
i++,j--;
for(int p=x;p<=i;p++){
for(int q=j;q<=y;q++){
if(i-p!=q-j&&a[p][q]==1){
flag=1;
break;
}
if(i-p==q-j&&a[p][q]!=1){
flag=1;
break;
}
}
if(flag){
break;
}
}
if(flag){
break;
}
cnt++;
b[i][j]=1;
}
ans=max(ans,cnt);
return;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
bool pd=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1&&b[i][j]==0){
pd=1;
search(i,j);
}
}
}
if(!pd){
printf("%d",0);
return 0;
}
printf("%d",ans);
return 0;
}by 陈彦锟 @ 2019-10-10 20:52:41
#include<bits/stdc++.h>
using namespace std;
int p,r,z,c,sum[2600][2600],a[2600][2600],n,m,ans,pd[2600][2600],num[2600][2600],ji;
int check(int e,int t){
for(int i=min(z,p);i<=max(z,p);i++){
if(sum[i][max(c,r)]-sum[i][min(c,r)-1]>1){
return 0;
}
}
return 1;
}
struct node{
int x;
int y;
int stemp;
}w;
node u;
queue<node> q;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i][j-1]+a[i][j];
if(a[i][j]==1){
u.x=i;
u.y=j;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
z=i,c=j;
q.push((node){i,j,1});
while(q.size()){
w=q.front();
q.pop();
p=w.x-1;
r=w.y+1;
if(p<=0||r>m){
break;
}
if(check(p,r)){
q.push((node){p,r,w.stemp+1});
}
ans=max(ans,w.stemp);
}
q.push((node){i,j,1});
while(q.size()){
w=q.front();
q.pop();
p=w.x+1;
r=w.y+1;
if(p>n||r>m){
break;
}
if(check(p,r)){
q.push((node){p,r,w.stemp+1});
}
ans=max(ans,w.stemp);
}
q.push((node){i,j,1});
while(q.size()){
w=q.front();
q.pop();
p=w.x+1;
r=w.y-1;
if(p>n||r<=0){
break;
}
if(check(p,r)){
q.push((node){p,r,w.stemp+1});
}
ans=max(ans,w.stemp);
}
q.push((node){i,j,1});
while(q.size()){
w=q.front();
q.pop();
p=w.x-1;
r=w.y-1;
if(p<=0||r<=0){
break;
}
if(check(p,r)){
q.push((node){p,r,w.stemp+1});
}
ans=max(ans,w.stemp);
}
}
if(i==u.x&&j==u.y){
break;
}
}
}
cout<<ans;
}