【题目链接：NYOJ-58】
经典的搜索问题，想必这题用广搜的会比较多，所以我首先使的也是广搜，但其实深搜同样也是可以的。
不考虑剪枝的话，两种方法实践消耗相同，但是深搜相比广搜内存低一点。
我想，因为广搜需要的就是队列，所以相比递归队列更耗内存？
当然DFS并不像上图所说，需要用栈，而是运用递归即可。
BFS：
因为BFS是要一个接一个的遍历，所以用到了结构体，来保存坐标和当前所走步数
1.每走一步，通过定义的结构体，从队列中提取a（即上一步的坐标、步数（步数每次累加））
2.在a的基础上进行对a周围四个方向进行判断，找出可以继续走的位置（即非障碍、边界），并将该位置的坐标，进入队列中
继续走下一步时，循环以上1.2两步操作
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int dir[][]= {,,-,,,,,-};
struct point{
int x,y,step;
};
int bfs(point s,point e,int map[][]){
queue<point>tp;//自定义类型的队列
int i;
point t;//保存当前坐标 ，临时变量
//s表示之前
//e表示目标
s.step=;//保存步数
map[s.x][s.y]=;//标记此处已经走过
tp.push(s);//初始化队列 ，s中(x,y)初始为起始坐标，step = 0
while(!tp.empty()){//循环直至队列为空
s=tp.front();//每次循环s都等于队首
tp.pop();//删除队首
if(s.x==e.x&&s.y==e.y)//如果当前坐标与目标坐标相等
return s.step; //返回当前的步数
//遍历四个不同的方向
//如果是通道（0），即增加步数
for(int i=; i<; i++){
t.x=s.x+dir[i][];
t.y=s.y+dir[i][];
if(map[t.x][t.y]==){//如果是通道
t.step=s.step+;
map[t.x][t.y]=;//标记此处已经走过，及标记为墙
tp.push(t);
}
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
point s,e;
int map[][]= {,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,};
scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
printf("%d\n",bfs(s,e,map));
}
return ;
}
DFS:
DFS就没什么好说了，不明白可以看看之前的DFS博客
只不过这里，没有用到单独的二维数组see[][]，来判断本个坐标是已经搜索过
而是结合题意，把当前所在位置变为'1'，即障碍、边界，那么在递归往下延伸判断四周时，达到同样的目的
当然在DFS函数最后，需要把Map[][]重新变为'0'，因为递归执行的顺序是自上而下再从下向上返回
因为是多组测试数据，所以需要在递归返回时，把迷宫“恢复原貌”
#include<iostream>
using namespace std;
#define min(a,b) a < b ? a : b
int Map[][] = {,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,};
int a,b,c,d,num;
void dfs(int x,int y,int s){
if(Map[x][y]) return;
if(x == c && y == d){
num = min(s,num);
return;
}
s++;
Map[x][y] = ;
dfs(x - ,y,s);
dfs(x + ,y,s);
dfs(x,y - ,s);
dfs(x,y + ,s);
Map[x][y] = ;
}
int main(){
int n;
cin >> n;
while(n--){
num = ;
cin >> a >> b >> c >> d;
dfs(a,b,);
cout << num << endl;
}
return ;
}
DFS,BFS讲解PPT:click here || there