1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution
{
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
    {
      int n = maze.size(), m = maze[0].size();
      int INF = 0x3f3f3f3f; // 表示无穷大
      std::vector<std::vector<int>> dist(n, std::vector<int>(m, INF));
      dist[entrance[0]][entrance[1]] = 0; // 入口步数初始化为 0

      using PII = std::pair<int, int>;
      std::queue<PII> q;
      q.push({entrance[0], entrance[1]});

      // 定义四个移动方向
      int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
      while (q.size())
      {
        PII t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for (int i = 0; i < 4; ++ i) // 尝试上下左右四个方向
        {
          int a = x + dx[i], b = y + dy[i];
          // 检查新位置是否有效
          if (a >= 0 && a < n && b >= 0 && b < m && maze[a][b] == '.' && dist[a][b] > dist[x][y] + 1)
          {
            dist[a][b] = dist[x][y] + 1; // 更新步数
            // 如果新位置是出口（在边界上）
            if (a == 0 || a == n - 1 || b == 0 || b == m - 1)
              return dist[a][b];
            q.push({a, b}); // 加入队列
          }
        }
      }
      return -1; // 无法找到出口
    }
};