开了博客之后一直没动今天水完题手痒想起这个就来水一篇陈年水题(雾
把每个格子的数字展开成二进制后就表示各方向上是否有墙.
直接用结构体存每个格子,读入的时候顺便处理一下.
然后直接bfs就好啦…(QwQ我一开始写判断的时候偷懒省了大括号成功的挂掉…
然后贴一下代码(QwQ跟别人比好像写的特别长…
#include<cstdio>
#include<queue>
using namespace std;
const int N=55;
struct point{bool w[4];}map[N][N];
struct p{int x,y;};
typedef queue<p> Queue;
int n,m,tmp,ans,num;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
bool vis[N][N];
Queue Q;
inline int max(int x,int y){return x>y?x:y;}
inline void decom(int x,int y,int s)
{
for(int i=0;i<4;i++)map[x][y].w[i]=s&1,s>>=1;
}
inline bool ok(int x1,int y1,int x,int y,int id)
{
if(vis[x][y])return 0;
if(x<1||y<1||x>n||y>m)return 0;
if(id==0){if(map[x1][y1].w[0]||map[x][y].w[2])return 0;}
else if(id==1){if(map[x1][y1].w[1]||map[x][y].w[3])return 0;}
else if(id==2){if(map[x1][y1].w[2]||map[x][y].w[0])return 0;}
else if(id==3){if(map[x1][y1].w[3]||map[x][y].w[1])return 0;}
return 1;
}
inline void bfs(int x,int y)
{
if(vis[x][y])return;
int temp=1;vis[x][y]=1;num++;
Q.push((p){x,y});
while(!Q.empty())
{
p t;t=Q.front();Q.pop();
for(int i=0;i<4;i++)
{
int tx=t.x+dx[i];int ty=t.y+dy[i];
if(ok(t.x,t.y,tx,ty,i))
{
vis[tx][ty]=1;temp++;
Q.push((p){tx,ty});
}
}
}ans=max(ans,temp);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&tmp),decom(i,j,tmp);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)bfs(i,j);
printf("%d\n%d",num,ans);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章