设有一m行n列迷宫,O为可到达点,X为不可到达点,S为起点,E为终点,有一小虫,想从S走到E。该虫只能上、下、左、右四个方向移动,且不能出界。求从S到E的最短“可行”路线.

Question

设有一m行n列迷宫，O为可到达点，X为不可到达点，S为起点，E为终点，有一小虫，想从S走到E。该虫只能上、下、左、右四个方向移动，且不能出界。求从S到E的最短“可行”路线.

Answer 1

• 以下回答由chatgpt基于相关博客总结生成:

  我可以给出一个经典的解决方案：广度优先搜索算法（BFS）。以下是具体的步骤：

  1.定义一个Node结构体，包含横坐标x、纵坐标y和当前位置走到的步数step。同时定义一个visited数组，记录每个位置是否被访问过（避免重复访问）。

  struct Node{ int x; int y; int step; }; bool visited[MAX][MAX];

  2.定义一个队列queue，初始状态将起点S入队列，并将S的visited值设为true。

  queueque; que.push((Node){start_x, start_y, 0}); visited[start_x][start_y] = true;

  3.定义四个方向向量dx[]和dy[]，用于表示上下左右四个方向，同时通过循环遍历每个在队列中的节点，对其四个方向进行拓展，即向队列中添加新的节点，并将其visited值设为true。

  int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; while(!que.empty()){ Node now = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int nx = now.x + dx[i]; int ny = now.y + dy[i]; if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == O && !visited[nx][ny]) { que.push((Node){nx, ny, now.step + 1}); visited[nx][ny] = true; if(nx == end_x && ny == end_y){ return now.step + 1; } } } }

  4.最后，如果队列中没有节点了，则表示无法到达终点E，返回-1.

  完整代码如下：（其中MAX表示迷宫的大小，m、n分别为行数和列数，start_x、start_y、end_x、end_y分别为起点和终点的横纵坐标，map表示迷宫的存储，O和X分别表示能够到达和不能到达的格子。）

  include

  include

  include

  include

  using namespace std;

  const int MAX = 1000; int m, n, start_x, start_y, end_x, end_y; char map[MAX][MAX]; bool visited[MAX][MAX];

  struct Node{ int x; int y; int step; };

  int bfs() { memset(visited, 0, sizeof(visited)); int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1};

  queue<Node>que;
  que.push((Node){start_x, start_y, 0});
  visited[start_x][start_y] = true;
  
  while(!que.empty()){
      Node now = que.front();
      que.pop();
      for(int i = 0; i < 4; i++) {
          int nx = now.x + dx[i];
          int ny = now.y + dy[i];
          if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] == 'O' && !visited[nx][ny]) {
              que.push((Node){nx, ny, now.step + 1});
              visited[nx][ny] = true;
              if(nx == end_x && ny == end_y){
                  return now.step + 1;
              }
          }
      }
  }
  return -1;
  

  }

  int main() { scanf("%d %d", &m, &n); getchar(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { scanf("%c", &map[i][j]); if(map[i][j] == 'S') { start_x = i; start_y = j; } else if(map[i][j] == 'E') { end_x = i; end_y = j; } } getchar(); }

  int ans = bfs();
  printf("%d\n", ans);
  
  return 0;
  

  }