AcWing 1098. 城堡问题

一、bfs

#include 
//这道题输入自带状态压缩;
using namespace std;
const int N = 55, M = N * N;
struct Node {
  int x;
  int y;
};

int n, m;
int g[N][N];    //地图
Node q[M];      //队列
bool st[N][N];  //标识是否走过

int dx[4] = {0, -1, 0, 1};  //左上右上
int dy[4] = {-1, 0, 1, 0};  //西北东南 1 2 4 8 二进制位运算，参考1098_0.cpp

int bfs(int sx, int sy) {
  int hh = 0, tt = -1;
  q[++tt] = {sx, sy};
  st[sx][sy] = true;

  //一次bfs跑一个连通块，统计一个连通块的面积
  int area = 0;

  while (hh <= tt) {
    Node t = q[hh++];
    area++;  //出队列时房间面积++

    for (int i = 0; i < 4; i++) {
      int x = t.x + dx[i], y = t.y + dy[i];
      if (x == 0 || x > n || y == 0 || y > m) continue;
      if (st[x][y]) continue;
      if (g[t.x][t.y] >> i & 1) continue;  //有墙
      //连通的房间入队列
      q[++tt] = {x, y};
      st[x][y] = true;
    }
  }
  return area;
}

int main() {
  cin >> n >> m;
  //虽然在题目中说的是二进制模拟的数字，但输入时不做处理，在使用时再用位运算处理
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) cin >> g[i][j];

  int cnt = 0, area = 0;  //房间数，最大面积
  //套路，枚举二维的每个非标识位置
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (!st[i][j]) {
        //从此点出发找连通块
        area = max(area, bfs(i, j));
        cnt++;  //记录连通块个数
      }

  cout << cnt << endl;
  cout << area << endl;
  return 0;
}

二、dfs

#include 
using namespace std;
const int N = 55;
int g[N][N];
int st[N][N];
int n, m, ans;  //注意这里的ans不能做为dfs参数进行传递，因为维护的是同一个变量

int dx[4] = {0, -1, 0, 1};  //左上右上
int dy[4] = {-1, 0, 1, 0};  //西北东南 1 2 4 8 二进制位运算，参考1098_0.cpp

void dfs(int sx, int sy) {
  st[sx][sy] = true;
  for (int i = 0; i < 4; i++) {
    int x = sx + dx[i], y = sy + dy[i];
    if (x == 0 || x > n || y == 0 || y > m) continue;
    if (st[x][y]) continue;
    if (g[sx][sy] >> i & 1) continue;  //自带数位压缩表示法~
    ans++;
    dfs(x, y);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) cin >> g[i][j];

  int cnt = 0, area = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (!st[i][j]) {
        cnt++;  //连通块数量
        ans = 1;
        dfs(i, j);
        area = max(area, ans);
      }
  cout << cnt << endl;
  cout << area << endl;
  return 0;
}