[刷题笔记] ybt1250：The Castle

Problem

Solution

显然bfs，只不过扩散的时候需要判断墙

那么如何判断墙呢？题目只给出了每个方块墙方向的和

原来的思路是可以暴力，很复杂但是可做，代码就不给了。

后来教练讲到了可以用位运算巧妙实现，这里重点介绍一下：

首先，我们观察一下每面墙代号的二进制：

有同学可以不怎么了解二进制，我们再举几个例子：

发现什么没有？判断有没有这面墙，令需要判断的数为\(x\)，判断x>>i&1如果为1，则有墙（i为西北东南四个方向，下标从0开始）
为什么这样可以？举个例子，对二进制0110判断，让其右移2位（判断东墙),右移完为0，则没有东墙，更没有南墙。

本题巧妙地运用了位运算使得代码变得简洁容易实现，位运算的用法还有很多，比如使用>>优化除法，这里不再赘述了,但是我们要学会在代码中运用位运算优化，这也是本题的妙处。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 1010
using namespace std;
typedef pair<int,int> PAIR;
int n,m;
int mapp[N][N];
int dx[4] = {0,-1,0,1}; //注意西北东南四个方向要按照顺序
int dy[4] = {-1,0,1,0};
int vis[N][N];
int maxn = -1,cnt = 0;
void bfs(int x,int y)
{
	queue <PAIR> q;
	q.push(PAIR(x,y));
	vis[x][y] = 1;
	int sum = 1;
	while(!q.empty())
	{
		maxn = max(maxn,sum);
		PAIR p =q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int ax = p.first+dx[i];
			int ay = p.second+dy[i];
			int flg = (mapp[p.first][p.second]>>i)&1;
			if(ax>=1&&ax<=n&&ay>=1&&ay<=m&&!vis[ax][ay]&&!flg)
			{
				sum++;
				vis[ax][ay] = 1;
				q.push(PAIR(ax,ay));
			}
		}
}
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) scanf("%d",&mapp[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) 
		{
			if(!vis[i][j]) 
			{
				vis[i][j] = 1;
				cnt ++;
				bfs(i,j);
			}
		}
	}
	cout<<cnt<<endl<<maxn<<endl;
	return 0;
}