题解 | #走迷宫#

广度优先BFS

#include <iostream>
#include <cstring>
#include <string>
#include <queue>

int main(int argc, char *argv[]) {
  int dx[4] = {1, -1, 0, 0};  // 两种对应下标搭配四个方向
  int dy[4] = {0, 0, -1, 1};  // BFS优先邻近点
  std::queue<std::pair<int, int>> point_queue;  // BFS先访问的点，其邻近点也先访问
  int n, m, start_x, start_y, end_x, end_y;
  
  std::cin >> n >> m;
  std::cin >> start_x >> start_y >> end_x >> end_y;
  
  char net[n+1][m+1];  
  int visited[n+1][m+1];   
  
  memset(net, 0, sizeof(net));   // 网，下标从1开始
  memset(visited, -1, sizeof(visited));   // 未访问为-1
  
  for (int i = 1; i <= n; i++) {  // 从（1，1）开始存储
    std::string temp;
    std::cin >> temp;
    std::memcpy(net[i]+1, temp.c_str(), temp.size());
  }
  
  point_queue.push({start_x, start_y});
  visited[start_x][start_y] = 0;  // 起点改变其访问状态，顺便充当计数器
  
  while (point_queue.size()) { // 邻近点加入队列，一直访问邻近点直到无路时栈空
    auto cur_point = point_queue.front();
    point_queue.pop();

    for (int i = 0; i < 4; i++) {
      int x = cur_point.first + dx[i], y = cur_point.second + dy[i];
      // 四个邻近点依次访问
      if (x >= 1 && x <= n && y >= 1 && y <= m && visited[x][y] == -1 && net[x][y] == '.') {
        visited[x][y] = visited[cur_point.first][cur_point.second] + 1;   // 标记访问并且计数
        point_queue.push({x, y});      // 邻近点入队（先访问先入）
      }
    }
  }
  
  std::cout << visited[end_x][end_y] << std::endl;   // 初值为-1，没有访问到则为-1
  
  return 0;
}