一道麻烦题～

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int m, n, room_id, wall_x, wall_y;
string wall_direction;
unordered_map<int, int> areas; // (room_id -> area)

int get_room_id(int x, int y, vector<vector<int>>& vis) {
  return x < 0 || y < 0 || x == n || y == m ? -1 : vis[y][x];
}

int dfs(vector<vector<int>>& g, vector<vector<int>>& vis, int x, int y) {
  // 西(west) ==》北(NORTH) ==》东(EAST) ==》南(SOUTH)
  static constexpr int dirs[][2] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; 

  int areas = 1;
  for (int i = 0; i < 4; ++i) {
    if (g[y][x] & 1 << i) continue; // wall

    int nx = x + dirs[i][0], ny = y + dirs[i][1];
    if (vis[ny][nx]) continue; // visited

    vis[ny][nx] = room_id; // mark as visited
    areas += dfs(g, vis, nx, ny);
  }

  return areas;
}

int main(void) {
  scanf("%d %d", &n, &m);
  vector<vector<int>> g(m, vector<int>(n, 0));
  vector<vector<int>> vis(m, vector<int>(n, 0));
  for (int y = 0; y < m; ++y)
    for (int x = 0; x < n; ++x) cin >> g[y][x];

  int components = 0, max_areas = 0; // components == 连通分量的个数
  for (int y = 0; y < m; ++y)
    for (int x = 0; x < n; ++x) {
      if (vis[y][x]) continue;
      ++room_id;
      vis[y][x] = room_id;
      areas[room_id] = dfs(g, vis, x, y);
      max_areas = max(max_areas, areas[room_id]);
      ++components;
    }

  const int dirs[][2] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; 

  // 去穷举每一间房子的每一面墙
  int new_max_areas = 0;
  for (int x = 0; x < n; ++x) { 
    for (int y = m - 1; y >= 0; --y) { // 实际证明我的思维还是比较缜密的，哟西！
      int curr_id = get_room_id(x, y, vis);
      for (int i = 0; i < 4; ++i) { // 一个有房间有0-4面墙
        if (g[y][x] & 1 << i) { // wall
          int nx = x + dirs[i][0], ny = y + dirs[i][1];
          int next_id = get_room_id(nx, ny, vis);
          if (next_id == curr_id) continue; // 其实就是在同一连通分量里 （房间）
          int area = areas[curr_id] + areas[next_id]; // merge area 
          if (area > new_max_areas) {
            wall_x = x, wall_y = y;
            new_max_areas = area;
            switch (i) {
              case 0: wall_direction = "W"; break;
              case 1: wall_direction = "N"; break;
              case 2: wall_direction = "E"; break;
              case 3: wall_direction = "S"; break;
            }
          }
        }
      }
    }
  }

  cout << components << endl << max_areas << endl;
  cout << new_max_areas << endl;
  cout << wall_y + 1 << ' ' << wall_x + 1  << ' ' << wall_direction << endl;
}

C 版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define N 50
#define ri register int

int m, n;
int g[N][N], visited[N][N];
int cnt_rooms, max_areas, areas; 
int wx, wy, wd; // 折墙的坐标与墙的朝向,折墙的方案数

// 精心设计的坐标模型
const int dirs[] = { 0, -1, 0, 1, 0 }; // 西北东南 (纵坐标在前, 横坐标在后)

int DFS(int x, int y) {
  visited[y][x] ^= 1;
  int areas = 1, nx, ny;
  for (int i = 0; i < 4; ++i) {
    if (g[y][x] & 1 << i) continue; // meet the wall
    ny = y + *(dirs + i), nx = x + *(dirs + i + 1);
    if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[ny][nx])
      continue; 
    areas += DFS(nx, ny);
  }
  return areas;
}

int main(int argc, char const *argv[]) {

  scanf("%d %d ", &n, &m);

  ri i, x, y;
  for (y = 0; y < m; ++y) {
    for (x = 0; x < n; ++x)
      scanf("%d", *(g + y) + x);
    getchar();
  }

  for (y = 0; y < m; ++y) {
    for (x = 0; x < n; ++x) {
      if (visited[y][x]) continue;
      ++cnt_rooms;
      max_areas = fmax(max_areas, DFS(x, y));
    }
  }

  printf("%d\n%d\n", cnt_rooms, max_areas);

  max_areas = 0;
  for (x = 0; x < n; ++x)
    for (y = m -1; y >= 0; --y)
      for (i = 0; i < 4; ++i)
        if (g[y][x] & 1 << i) { // 暴力拆除每一堵墙
          memset(visited, 0x0000, sizeof visited);
          g[y][x] -= 1 << i;
          areas = DFS(x, y);
          g[y][x] |= 1 << i; // 回溯
          if (areas > max_areas) {
            wx = x + 1, wy = y + 1, wd = i;
            max_areas = areas;
          }
        }

  char d;
  if (wd == 0) d = 'W';
  else if (wd == 1) d = 'N';
  else if (wd == 2) d = 'E';
  else d = 'S';

  printf("%d\n", max_areas);
  printf("%d %d %c\n", wy, wx, d);
  return 0;
}