迷宫

BFS 与 最短路

#include<bits/stdc++.h>
using namespace std;
struct node{
  int x;
  int y;
  //(1)简单方法：
  string path;                   //path,记录从起点(0,0)到这个点(x,y)的完整路径
};
char mp[31][51];                 //存地图
char k[4]={'D','L','R','U'};     //字典序
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int vis[30][50];                  //标记。vis=1: 已经搜过，不用再搜

//(2)标准方法：
char pre[31][51];                 // 用于查找前驱点。例如pre[x][y] = ‘D’，表示上一个点
//往下走一步到了(x,y)，那么上一个点是(x-1,y)
void print_path(int x,int y){     //打印路径：从(0,0)到(29,49)
  if(x==0 && y==0) return;        //回溯到了起点，递归结束，返回
  if(pre[x][y]=='D') print_path(x-1,y);                //回溯，往上 U
  if(pre[x][y]=='L') print_path(x, y+1);               //回溯，往右 R
  if(pre[x][y]=='R') print_path(x, y-1);
  if(pre[x][y]=='U') print_path(x+1,y);
  printf("%c",pre[x][y]);        //最后打印的是终点
}
void bfs(){
  node start; start.x=0; start.y=0;
  //(1)简单方法：
  start.path="";
  vis[0][0]=1;                   //标记起点被搜过
  queue<node>q;
  q.push(start);                 //把第一个点放进队列，开始BFS
  while(!q.empty()){
    node now = q.front();        //取出队首
    q.pop();
    if(now.x==29 && now.y==49){  //第一次达到终点，这就是字典序最小的最短路径
      //(1)简单方法：打印完整路径
      cout << now.path << endl;
      //(2)标准方法：打印完整路径，从终点回溯到起点，打印出来是从起点到终点的正序
      //print_path(29,49);
      return;
    }
    for(int i=0;i<4;i++){         //扩散邻居结点
      node next;
      next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1];
      if(next.x<0||next.x>=30||next.y<0||next.y>=50)   //越界了
        continue;
      if(vis[next.x][next.y]==1 || mp[next.x][next.y]=='1')
        continue;                //vis=1:已经搜过; mp=1:是障碍
      vis[next.x][next.y]=1;     //标记被搜过
      //(1)简单方法：记录完整路径：复制上一个点的路径，加上这一步
      next.path = now.path + k[i];
      //(2)标准方法：记录点(x,y)的前驱
      pre[next.x][next.y] = k[i];
      q.push(next);
    }
  }
}
int main(){
  for(int i=0;i<30;i++) cin >> mp[i];                 //读题目给的地图数据
  bfs();
}

笔记：BFS是逐层扩散，在长度相同的条件下，谁先到达起点，那条路径就是最短路径，所以在特定的题目里BFS可以求出最短路径