更新时间:2022-08-12 16:30:59
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; }