原题在这
信息
语言 C++
算法 BFS
问题 测试点2 测试点7 答案错误,其余(包括 原题数据和自设数据)均可通过
代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,F[4][2]={{0,-1},{-1,0},{0,1},{1,0}},T,W,Room_sum,Room_max;
struct Node
{
int x,y,wall[4],B;
}map[55][55],Q[100001],S,L;
void print()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<map[i][j].B;
}
cout<<endl;
}
}
int BFS()
{
int sum=0;
T=1;
W=0;
W++;
Q[W]=S;
while(T<=W)
{
S=Q[T];
L=S;
T++;
for(int i=0;i<4;i++)
{
S.x+=F[i][0];
S.y+=F[i][1];
if(S.x>=0 && S.x<n && S.y>=0 && S.y<m && map[S.x][S.y].B==0 && map[L.x][L.y].wall[i]==0)
{
sum++;
W++;
Q[W]=S;
map[S.x][S.y].B=1;
}
S.x-=F[i][0];
S.y-=F[i][1];
}
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int w;
cin>>w;
map[i][j].wall[3]=(w>=8);
w-=map[i][j].wall[3]*8;
map[i][j].wall[2]=(w>=4);
w-=map[i][j].wall[2]*4;
map[i][j].wall[1]=(w>=2);
w-=map[i][j].wall[1]*2;
map[i][j].wall[0]=(w>=1);
w-=map[i][j].wall[0]*1;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j].B==0)
{
int x;
Room_sum++;
S.x=i;
S.y=j;
x=BFS();
Room_max=(x>Room_max?x:Room_max);
}
}
}
cout<<Room_sum<<endl<<Room_max;
}