poj 3984 迷宫问题
程序员文章站
2022-05-20 22:50:51
...
本文章纯属为了记录自己的萌新acm之路 请高手勿喷 有错误可指出感谢
我也是参考了 https://blog.csdn.net/qq_41552508/article/details/79501849 的思路感谢
以下是个人见解:
此题应该不难看出是bfs 如果要求路径的步数 当然就是dfs
dfs一直搜到底
bfs 一层一层的搜 类似一楼搜完搜二楼 二楼搜完搜三楼。。。
bfs可以存路径 要是求路径题就递归回去 打印存好的路径就可以了
先存图 然后模拟每次走4个方向的路 符合条件的存入结构体数组中 记录每条点的上一个点所存的位置 如果到终点 递归回去 打印存好的路径就可以了
上代码 代码详解请看注释
#include<iostream>
using namespace std;
int ch[8][8]; //用来存图
int mark[8][8]; //用来标记
int next[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //控制每一步走的方向
int head,tail; //队列的头和尾
struct node{
int x;
int y;
int n; //记录上一步的位置为后面递归打印路径使用
}que[36];
void p(int head){
while(que[head].n!=-1){
p(que[head].n); //递归打印所走过的路径 这里就能看出n的作用了
printf("(%d, %d)\n",que[head].x,que[head].y); //逗号后有空格
return ;
}
printf("(0, 0)\n"); //递归到开始点时打印出发点 注意这个答案逗号后有空格
}
void b(){
que[0].x=0;
que[0].y=0;
que[0].n=-1; //初始出发点的n 也作为递归打印路径的条件
tail++;
struct node now;
while(head<tail){
if(que[head].x==4&&que[head].y==4){ //走到终点
p(head); //开始打印路径 head相当于位置
return ;
}
for(int i=0;i<4;i++){ //模拟4个方向
now.x=que[head].x+next[i][0];
now.y=que[head].y+next[i][1];
now.n=head; //记录上一个点的位置
if(now.x>=0&&now.x<5&&now.y>=0&&now.y<5){ //边界条件
if(!mark[now.x][now.y]&&!ch[now.x][now.y]){
mark[now.x][now.y]=1;
que[tail]=now;
tail++;
}
}
}
head++;
}
return ;
}
int main(){
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>ch[i][j];
b();
return 0;
}
上一篇: 对于dfs剪枝的分析
下一篇: 浅谈宋朝的祠禄官制度,在历史上有何影响?