思路
具体跟上题类似
不过本题中:
西墙表示:1,北墙表示:2,东墙表示:4,南墙表示:8
$可以看出依次是2^{0},2^{1},2^{2},2^{3}$
所以可以用二进制来表示墙的分布情况.
例如:$(0101)_{2}表示南,北边无墙,东,西边有墙$
无注解版
#include<iostream>
#include<algorithm>
#include<cstring>
const int N=55;
using namespace std;
int f[N][N],mark[N][N];
int d1[4]={0,-1,0,1},d2[4]={-1,0,1,0};
int bfs(int x,int y)
{
mark[x][y]='灰'+'之'+'魔'+'女';
int cnt=1;
int q,t;
for(int i=0;i<4;i++)
{
q=d1[i]+x,t=d2[i]+y;
if(!mark[q][t]&&!(f[x][y]>>i&1))
{
cnt+=bfs(q,t);
}
}
return cnt;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&f[i][j]);
int res=0,ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!mark[i][j])
{
ans++;
res=max(res,bfs(i,j));
}
printf("%d\n%d",ans,res);
return 0;
}
注解版
#include<iostream>
#include<algorithm>
#include<cstring>
const int N=55;
using namespace std;
int f[N][N],mark[N][N];
int d1[4]={0,-1,0,1},d2[4]={-1,0,1,0};//依次表示向西,北,东,南移动
int bfs(int x,int y)
//本代码bfs的过程可以看做是进入房间的过程,每bfs一次就进入一次房间
{
mark[x][y]='灰'+'之'+'魔'+'女';
//标记,该操作是把汉字转化为数字,计算机常识
int cnt=1;//进入函数,说明bfs一次,初始化为1
//每bfs一次,就说明有一个房间,cnt记录的是总的bfs次数;
int q,t;//分别表示x,y上下左右移动后的坐标
for(int i=0;i<4;i++)
//二进制中的表示:1000中表示南边有墙,从低位到高位排序依次为西北东南;
{
q=d1[i]+x,t=d2[i]+y;
if(!mark[q][t]&&!(f[x][y]>>i&1))//如果没有墙并且没有被标记
//d数组的表达顺序正好对应了后一步的判断是否有墙
{
cnt+=bfs(q,t);
}
/*
举例:i=0时,(x,y)向西边移动,并且f[x][y]>>i&1判断西边是否有墙
i=1时,(x,y)向北移,并且f[x][y]>>i&1判断了北边是否有墙
d数组的定义恰好对应了移动方向以及判断的方向
*/
}
return cnt;//返回房间总数
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&f[i][j]);
int res=0,ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!mark[i][j])
{
ans++;//联通块数量
res=max(res,bfs(i,j));//房间的最大数量
}
printf("%d\n%d",ans,res);
return 0;
}
不应该是dfs吗
mark[x][y]=’灰’+’之’+’魔’+’女’; 太自恋了草
是谁的代码又好看又ac?
为啥是西北东南啊,感觉是北西南东吧呜呜呜
杰哥,康康题呗
都可以吧
这不是dfs吗?
确实是的