BFS Algorithm! （被输入的地图的格式给坑了！)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using P = pair<int, int>;
static constexpr int dirs[] { 0, -1, 0, 1, 0 }; // up --> left --> down --> right

int n, m; // n == width, m == height

bool check(vector<string>& g, int x, int y, int offset_x, int offset_y) {
  return g[2 * y - 1 + offset_y][2 * x - 1 + offset_x] == ' ';
}

void print(vector<vector<int>>& mat) {
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j)
      printf("%3d ", mat[i][j]);
    printf("\n");
  }
  printf("\n");
}

void bfs(vector<string>& g,
         vector<vector<vector<int>>>& dist, 
         int sx, int sy, int k) {

  queue<P> q;
  vector<vector<int>> seen(m + 1, vector<int>(n + 1, 0));
  q.emplace(sx, sy);
  seen[sy][sx] = 1;

  int steps = 1;
  while (not q.empty()) {
    size_t sz = q.size();
    while (sz--) {
      const auto [x, y] = q.front(); q.pop();
      dist[k][y][x] = steps;
      for (int i = 0; i < 4; ++i) {
        const int nx = x + dirs[i], ny = y + dirs[i + 1];
        if (nx < 1 || nx > n || ny < 1 || ny > m 
            || !check(g, x, y, dirs[i], dirs[i + 1]) || seen[ny][nx])
          continue;
        q.emplace(nx, ny);
        seen[ny][nx] = 1;
      }
    }
    ++steps;
  }
}

int main(void) {
  cin >> n >> m;
  vector<vector<vector<int>>> dist(2, vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));

  const int h = m << 1 | 1;
  vector<string> g(h);
  getchar();
  for (int i = 0; i < h; ++i)
    getline(cin, g[i]);

  int k = 0;
  // left and right boundary
  for (int y = 1; y <= m; ++y) {
    if (check(g, 1, y, -1, 0)) bfs(g, dist, 1, y, k++);
    if (check(g, n, y, 1, 0))  bfs(g, dist, n, y, k++);
  }

  // top and bottom boundary
  for (int x = 1; x <= n; ++x) {
    if (check(g, x, 1, 0, -1)) bfs(g, dist, x, 1, k++);
    if (check(g, x, m, 0, 1))  bfs(g, dist, x, m, k++);
  }

  int ans = 0;
  for (int y = 1; y <= m; ++y)
    for (int x = 1; x <= n; ++x)
      ans = max(ans, min(dist[0][y][x], dist[1][y][x]));

  printf("%d\n", ans);
  return 0;
}

复习提高版

#include <iostream>
#include <cstring>

#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)

using namespace std;
const int W = 40, H = 105;
constexpr int dirs[] { 0, -1, 0, 1, 0 };

struct Coordinate {
  int x, y;
  Coordinate() : Coordinate(-1, -1) {}
  Coordinate(int _x, int _y) : x(_x), y(_y) {}
} q[(H << 1) * (W << 1)];

int w, h, x1, y1, x2, y2, ans;
char board[H << 1][W << 1];
int dists1[H << 1][W << 1], dists2[H << 1][W << 1];

inline void print_board(void) {
  putchar(10);
  f(y, 0, (h << 1 | 1)) f(x, 0, (w << 1 | 1)) printf("%c%c", board[y][x], x == w << 1 ? 10 : 0);
}

inline void BFS(int sx, int sy, int dists[][W << 1]) {

  int front = 0, rear = 0;
  q[rear++] = {sx, sy};
  dists[sy][sx] = 0;

  int steps = 0;
  while (front < rear) {
    size_t s = rear - front;
    while (s--) {
      const int x = q[front].x, y = q[front].y; ++front;
      f(d, 0, 4) {
        int nx = x + dirs[d], ny = y + dirs[d + 1];
        if (nx < 0 or nx > w << 1 or ny < 0 or ny > h << 1 or board[ny][nx] != 32)
          continue;
        if (x != sx or y != sy) {
          if (d == 0 or d == 2)
            ny = y + (dirs[d + 1] << 1);
          else
            nx = x + (dirs[d] << 1);
        }
        if (dists[ny][nx] >= 0) continue;
        q[rear++] = {nx, ny};
        dists[ny][nx] = steps + 1;
      }
    }
    ++steps;
  }
}

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

  // freopen("test.in", "r", stdin);

  scanf("%d%d", &w, &h);
  x1 = x2 = y1 = y2 = -1;

  string s;
  getchar();
  f(y, 0, (h << 1 | 1)) {
    getline(cin, s);
    f (x, 0, (w << 1 | 1)) {
      board[y][x] = s[x];
      if (x == 0 or x == w << 1 or y == 0 or y == h << 1 ) {
        if (board[y][x] == ' ') {
          if (x1 == -1) x1 = x, y1 = y;
          else x2 = x, y2 = y;
        }
      } 
    }
  }
  // print_board();
  // printf("%d %d %d %d\n", y1, x1, y2, x2);

  memset(dists1, -1, sizeof dists1);
  BFS(x1, y1, dists1);

  memset(dists2, -1, sizeof dists2);
  BFS(x2, y2, dists2);

  f(y, 0, (h << 1 | 1))
    f(x, 0, (w << 1 | 1))
      ans = max(ans, min(dists1[y][x], dists2[y][x]));

  // fclose(stdin);
  return printf("%d", ans), 0;
}