城堡问题

非递归实现本质就是手工模拟系统栈的操作，这里使用stack与pair进行模拟。需要注意的是，传统的递归转非递归，需要将子问题逆向地加入栈。在《城堡问题》中，这并不是必要的，原因是四个方向的搜索顺序并不影响最终的结果。

以下是城堡问题 - DFS递归实现的非递归实现：

#include <cstdio>
#include <algorithm>
#include <stack>
#include <utility>

using namespace std;

const int DIR = 4;
const int dx[] = { 0, -1, 0, 1 };
const int dy[] = { -1, 0, 1, 0 };
const int masks[] = { 1, 2, 4, 8 };

int m, n;
int g[51][51];
int f[51][51] = { 0 };

bool inRange(int x, int y) {
  return x >= 0 && x < m && y >= 0 && y < n;
}

int dfs(int x, int y) {
  stack<pair<int, int> > s;
  s.push(make_pair(x, y));
  int sum = 0;
  while (!s.empty()) {
    pair<int, int> top = s.top();
    s.pop();
    x = top.first, y = top.second;
    if (f[x][y] > 0) continue;
    f[x][y] = 1;
    sum++;
    for (int i = 0; i < DIR; i++) {
      int xx = x + dx[i], yy = y + dy[i];
      if (!inRange(xx, yy)) continue;
      if ((g[x][y] & masks[i]) != 0) continue;
      if ((g[xx][yy] & masks[(i + 2) % DIR]) != 0) continue;
      s.push(make_pair(xx, yy));
    }
  }
  return sum;
}

int main() {
  int i, j;
  scanf("%d%d", &m, &n);
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &g[i][j]);

  int roomNum = 0, maxArea = 0;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      if (f[i][j] == 0) {
        maxArea = max(maxArea, dfs(i, j));
        roomNum++;
      }
    }
  }
  printf("%d\n%d\n", roomNum, maxArea);

  return 0;
}

Recursive

自己手敲了一下递归实现，与视频不同的地方有：

使用了一个数组记录方向与位运算的mask
增加边界判断，视频中貌似没有进行边界判断，不知道是否存在下标越界问题
使dfs函数直接返回值而没有用全局变量记录
代码如下：

#include <cstdio>
#include <algorithm>

using namespace std;

const int DIR = 4;
const int dx[] = { 0, -1, 0, 1 };
const int dy[] = { -1, 0, 1, 0 };
const int masks[] = { 1, 2, 4, 8 };

int m, n;
int g[51][51];
int f[51][51] = { 0 };

bool inRange(int x, int y) {
  return x >= 0 && x < m && y >= 0 && y < n;
}

int dfs(int x, int y) {
  if (f[x][y] > 0)
    return 0;

  f[x][y] = 1;
  int sum = 1;
  for (int i = 0; i < DIR; i++) {
    int xx = x + dx[i], yy = y + dy[i];
    if (!inRange(xx, yy)) continue;
    if ((g[x][y] & masks[i]) != 0) continue;
    if ((g[xx][yy] & masks[(i + 2) % DIR]) != 0) continue;
    sum += dfs(xx, yy);
  }
  return sum;
}

int main() {
  int i, j;
  scanf("%d%d", &m, &n);
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &g[i][j]);

  int roomNum = 0, maxArea = 0;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      if (f[i][j] == 0) {
        maxArea = max(maxArea, dfs(i, j));
        roomNum++;
      }
    }
  }
  printf("%d\n%d\n", roomNum, maxArea);

  return 0;
}