【刷题】搜索——BFS：城堡问题(The Castle)

题目

题目链接

找出房间个数——>求连通块个数
最大房间——>求最大连通块

直接用flood fill算法

注意题目的输入，例如$11=8+2+1$，则代表有西、北、南墙

代码（Flood Fill）

上下左右的走向可以预先设置数组dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
墙的表示相当于二进制编码，可以用位运算获取特定位的数值(p[t.x][t.y] >> i & 1

#include <iostream>
#define x first
#define y second
using namespace std;int n, m;
int p[55][55];
bool st[55][55];
typedef pair<int, int> PII;
PII q[2505];int bfs(int i, int j) {int hh = 0, tt = 0;int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};q[0] = {i, j};st[i][j] = true;while(hh <= tt) {PII t = q[hh ++ ];for (int i = 0; i < 4; i ++ ) {int tx = t.x + dx[i], ty = t.y + dy[i];if (tx < 0 || tx >= m || ty < 0 || ty >= n) continue; // 越界 if (st[tx][ty]) continue;	// 已经走过 if ((p[t.x][t.y] >> i) & 1) continue;	// 是墙 q[ ++ tt ] = {tx, ty};	// 入队 st[tx][ty] = true;}}return tt + 1;	// 队列同时有的元素个数，就是连通块大小 
}int main () {scanf("%d%d", &m, &n);for (int i = 0; i < m; i ++ ) {for (int j = 0; j < n; j ++ ) {scanf("%d", &p[i][j]);} }int max_s = 0, cnt = 0;for (int i = 0; i < m; i ++ ) {for (int j = 0; j < n; j ++ ) {if (st[i][j]) continue;max_s = max(max_s, bfs(i, j));cnt ++;} }printf("%d\n%d\n", cnt, max_s);return 0;
}

代码（并查集）

将房间连通也可用并查集，枚举每个房间和两个方向（东、南；西、北；西、南；东、北皆可），如果没墙则连通，集合总数-1，集合元素个数相加。
注意集合元素个数初始都是1，ares初始也为1，因为连通块最小也有1个房间

#include <iostream>
using namespace std;int m, n;
int g[55][55];
const int dx[2] = {1, 0}, dy[2] = {0, 1};	// 向南、向东 
const int dw[2] = {8, 4};	// 南墙、东墙int p[2505], np[2505];
int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
} 
int main() {scanf("%d%d", &m, &n);for (int i = 0; i < m; i ++ ) {for (int j = 0; j < n; j ++ ) {scanf("%d", &g[i][j]);}}for (int i = 0; i < m * n; i ++ ) p[i] = i, np[i] = 1;int cnt = m * n, ares = 1;for (int i = 0; i < m; i ++ ) {for (int j = 0; j < n; j ++ ) {for (int k = 0; k < 2; k ++ ) {int tx = i + dx[k], ty = j + dy[k];if (tx >= m || ty >= n) continue; if (g[i][j] & dw[k]) continue;	// 是墙 int a = find(i * n + j), b = find(tx * n + ty);	// 找到{i,j}和{tx,ty}的祖先 if (a != b) {p[a] = b;	// a合并到b cnt -- ;	// 集合总数-1 np[b] += np[a];	// a元素加到b ares = max(ares, np[b]);}}}}printf("%d\n%d\n", cnt, ares);return 0;
}