AcWing 1097. 池塘计数

题目传送门

一、总结

\(Flood \ Fill\)问题比较经典的作法有两种：宽搜和深搜，代码写好的话，两种方法没有区别，不存在说数据量大了就深搜不了的问题。

要严格使用\(yxc\)老师讲的\(hh=0,tt=-1\)的模拟队列方式，不要使用\(STL\)中的\(queue\)!，原因很简单，有时候，比如斜率优化中，我们可能还要从队头出队列，那样的话还需要使用双端队列，还如直接来这个模拟更方便！

二、广度优先搜索

#include 

using namespace std;

const int N = 1010, M = N * N;
//方向数组
int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};

struct Node {
  int x;
  int y;
};

int n, m;
char g[N][N];
Node q[M];
int ans;

//宽搜
void bfs(int sx, int sy) {
  int hh = 0, tt = -1;
  q[++tt] = {sx, sy};  //放入起点
  g[sx][sy] = '.';

  while (hh <= tt) {
    Node t = q[hh++];
    for (int i = 0; i < 8; i++) {
      int x = t.x + dx[i];
      int y = t.y + dy[i];
      if (g[x][y] == 'W') {
        g[x][y] = '.';
        q[++tt] = {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];
  //枚举每个位置
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (g[i][j] == 'W') {
        bfs(i, j);
        ans++;
      }
  printf("%d\n", ans);
  return 0;
}

三、深度优先搜索

#include 

using namespace std;
const int N = 1010;
int n, m, ans;
char g[N][N];
//方向数组
int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};

void dfs(int x, int y) {
  g[x][y] = '.';  //这样可以不用使用st数组，妙！
  for (int i = 0; i < 8; i++)
    if (g[x + dx[i]][y + dy[i]] == 'W') dfs(x + dx[i], y + dy[i]);
}
int main() {
  cin >> n >> m;
  //使有深度优先搜索时，注意下标从1开始，这样相当于构建了一个四周为0的墙，不会越界
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) cin >> g[i][j];

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (g[i][j] == 'W') {  //找到“ W ”.
        dfs(i, j);
        ans++;  //统计答案
      }
  printf("%d\n", ans);
  return 0;
}