题目
思路
三遍DFS求解
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=50+5;
int a[maxn][maxn][maxn][maxn],large[maxn][maxn];
bool vis[maxn][maxn];
int cnt,Max,tot;
void dfs(int x,int y){
if(vis[x][y])return ;
cnt++;
vis[x][y]=1;
if(a[x][y][x+1][y])dfs(x+1,y);
if(a[x][y][x][y+1])dfs(x,y+1);
if(a[x][y][x-1][y])dfs(x-1,y);
if(a[x][y][x][y-1])dfs(x,y-1);
return;
}
void dfs2(int x,int y,int i,int j){
if(vis[x][y])return ;
large[x][y]=large[i][j];
vis[x][y]=1;
if(a[x][y][x+1][y])dfs2(x+1,y,i,j);
if(a[x][y][x][y+1])dfs2(x,y+1,i,j);
if(a[x][y][x-1][y])dfs2(x-1,y,i,j);
if(a[x][y][x][y-1])dfs2(x,y-1,i,j);
return;
}
bool dfs3(int i,int j,int k,int l){
if(i==k&&j==l)return 1;
if(vis[i][j])return 0;
vis[i][j]=1;
int xx=0;
if(a[i][j][i+1][j])xx=xx|dfs3(i+1,j,k,l);
if(a[i][j][i][j+1])xx=xx|dfs3(i,j+1,k,l);
if(a[i][j][i-1][j])xx=xx|dfs3(i-1,j,k,l);
if(a[i][j][i][j-1])xx=xx|dfs3(i,j-1,k,l);
return xx;
}
bool judge(int i,int j,int k,int l){
if(k==0||l==0||k>n||l>m)return 0;
memset(vis,0,sizeof(vis));
if(dfs3(i,j,k,l))return 0;
return 1;
}
int main(){
scanf("%d%d",&m,&n);
int temp;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&temp);
if(temp>=8)temp-=8;
else a[i][j][i+1][j]=1;
if(temp>=4)temp-=4;
else a[i][j][i][j+1]=1;
if(temp>=2)temp-=2;
else a[i][j][i-1][j]=1;
if(temp>=1)temp-=1;
else a[i][j][i][j-1]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]){
tot++;
cnt=0;
dfs(i,j);
large[i][j]=cnt;
Max=max(Max,cnt);
}
}
}
memset(vis,0,sizeof(vis));
printf("%d
%d
",tot,Max);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]){
dfs2(i,j,i,j);
}
}
}
memset(vis,0,sizeof(vis));
int ans=0;
int aa=0,bb=0,rel=0;
for(int j=1;j<=m;j++){
for(int i=n;i>=1;i--){
if(a[i][j][i-1][j]==0){
if(judge(i,j,i-1,j)){
if(ans<large[i][j]+large[i-1][j]){
ans=large[i][j]+large[i-1][j];
aa=i,bb=j,rel=1;
}
}
}
if(a[i][j][i][j+1]==0){
if(judge(i,j,i,j+1)){
if(ans<large[i][j]+large[i][j+1]){
ans=large[i][j]+large[i][j+1];
aa=i,bb=j,rel=2;
}
}
}
}
}
printf("%d
%d %d ",ans,aa,bb);
if(rel==1)printf("N
");
else printf("E
");
}