BFS和DFS的路径输出

DFS 其实就是一直顺着一个方向不断的搜索直到找到了目标为止。路径输出的时候，利用记录前面的点即可。

举例：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 9

int cnt;
struct Point{
   int x;
   int y;
}path[N*N];
int maze[N][N];/*保存地图*/
int vis[N][N];/*标记哪一个点是否被访问过*/
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};/*方向数组*/
Point star , end;

/*路径输出，只要找到了目标就可以输出*/
void output(){
   printf("(%d , %d)->" , star.x , star.y);
   for(int i = 1 ; i < cnt-1 ; i++)
      printf("(%d , %d)->" , path[i].x , path[i].y);
   printf("(%d , %d)\n\n" , end.x , end.y);
   printf("\n");
}

/*深搜*/
void DFS(int x , int y , int step){
   int tmp_x , tmp_y;
   Point p;
 /*如果找到了目标，就调用output函数输出路径，然后return*/
 if(x == end.x && y == end.y){
      cnt = step;
      output();
      return;
   }
   for(int i = 0 ; i < 4 ; i++){
      tmp_x = x+dir[i][0];
      tmp_y = y+dir[i][1];
      p.x = tmp_x;
      p.y = tmp_y;
      if(!maze[tmp_x][tmp_y] && !vis[tmp_x][tmp_y]){
        vis[x][y] = 1;
        path[step] = p;/*标记前面一个点*/
        DFS(tmp_x , tmp_y , step+1);
        vis[x][y] = 0;/*回溯*/
      }
   }
}

int main(){
   memset(vis , 0 , sizeof(vis));
   DFS(star.x , star.y , 1);
   return 0;
}

BFS就是不断向四周扩展，然后找到目标节点；利用数组模拟队列（或者直接利用STL的队列，但是STL里面的队列对于保存路径有点麻烦），适用与求最小步数等。

举例：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

#define MAXN 500010
#define N 10

int ans , end;
int sx , sy , ex , ey;/*sx sy是起点坐标，ex ey是终点坐标*/
int vis[N][N];
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};/*顺时针8个方向*/
char mp[N][N];
struct Point{/*结构体保存点的信息*/
   int x;
   int y;
   int pre;/*保存之前一个点的下标*/
   int d;/*保存来自哪一个方向*/
   int step;/*当前的步数*/
}p[MAXN];/*节点数组*/

void BFS(){
    int front , rear;
    front = 0 , rear = 1;/*初始化*/

    memset(vis , 0 , sizeof(vis));/*初始化为0*/
 /*初始化队列头节点的值*/
  p[front].x = sx , p[front].y = sy;
    p[front].pre = 0 , p[front].step = 0;
    vis[sx][sy] = 1;/*第一个点标记为1*/

    while(front < rear){
       Point tmp = p[front];/*取出队列的头然后头指针加加*/
       if(tmp.x == ex && tmp.y == ey){/*如果找到了*/
          end = front;/*记下最后一个点的下标*/
          ans = tmp.step;  /*求出最短的步数*/
          break;
       }
       front++;/*front相当与是STL的q.pop()*/
       for(int i = 0 ; i < 8 ; i++){/*枚举8个方向*/
          if(tmp.x+dir[i][0] <= 0 || tmp.x+dir[i][0] > 8)
            continue;
          if(tmp.y+dir[i][1] <= 0 || tmp.y+dir[i][1] > 8)
            continue;
          if(vis[tmp.x+dir[i][0]][tmp.y+dir[i][1]])
            continue;
          vis[tmp.x+dir[i][0]][tmp.y+dir[i][1]] = 1;/*标记为走过*/
          p[rear].x = tmp.x+dir[i][0] , p[rear].y = tmp.y+dir[i][1];
          p[rear].pre = front-1;/*记下前面一个的下标即为front-1*/
          p[rear].d = i;/*记下来自哪一个方向*/
          p[rear++].step = tmp.step+1;/*步数加1*/
       }
    }
}

/*利用回溯输出*/
void output(int x){
    if(x == 0)/*如果下标为0说明到达起点，那么回溯回去输出*/
      return;
    output(p[x].pre);
    printf("%s\n" , mp[p[x].d]);/*这里用到了方向的映射，比如上就是“U”*/
}

int main(){
    scanf("%d%d%d%d" , &sx , &sy , &ex , &ey);/*输入起点和终点的坐标*/
    BFS();
    printf("%d\n" , ans);
    output(end);
    return 0;
}