58-最少步数
内存限制:64MB
时间限制:3000ms
特判: No
难度:4
题目描述
这有一个迷宫，有0~8行和0~8列：
1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,1
0表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）
输入描述:
第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列
输出描述:
输出最少走几步。
样例输入:
复制
2
3 1 5 7
3 1 6 7
样例输出:
12
11
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int dis[4][2]= {
1,0,-1,0,0,1,0,-1};
struct point
{
int x,y,tenp;
};
int bfs(point s,point e,int map[9][9])//
{
queue<point>q;//栈
int i;
point t;
s.tenp=0;//初始步数
map[s.x][s.y]=1;//图开始的搜索；
q.push(s);
while(!q.empty())//栈的模板
{
s=q.front();
q.pop();
if(s.x==e.x&&s.y==e.y)//判为不能通过或者达到目标；
return s.tenp;//返回步数
for(i=0; i<4; i++)//遍历四个方向
{
t.x=s.x+dis[i][0];
t.y=s.y+dis[i][1];
if(map[t.x][t.y]==0)
{
t.tenp=s.tenp+1;
map[t.x][t.y]=1;
q.push(t);
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
point s,e;
int map[9][9]= {
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,
};
scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
printf("%d\n",bfs(s,e,map));
}
return 0;
}
bfs和dfs的个人简单整。
bfs搜索是
0110
1111
1111
0110
比如
0110
初次遇到1，开始搜索，左边是0结束，所以为1步。
关于bfs可以说简单一点就是，下面介绍bfs搜索的一个简单的过程：
以 5 代表搜索的一个开始，&代表没有走过的点。
开始：
&&&&&&
&&&&&&
&&&&&&
第一步：
&&&&&&
&&&5&&
&&&&&&
第二步：
&&&5&&
&&555&
&&&5&&
第三步：
&&555&
&55555
&&555&
你可以看的得出，bfs是一个怎么样的一个过程，总结起来就是每一个走过的点都会同时进行下一次的搜索，基本是四个方向。
而我们可以对比dfs；
第一步：
&&&&&&
&&5&&&
&&&&&&
第一步：
&&&&&&
&&55&&
&&&&&&
第二步：
&&&&&&
&&55&&
&&&5&&
第三步：
&&&&&
&&55&&
&&&55&
找到目标就回溯，每一次都可以选择四个方向走，这样一步一步的走。
对于这题：可能的结果很多，每一次搜索到的结果很多个，这个时间复杂度是很大的，所以我超时了。
小结：
关于BFS，它搜索的特性，我们可以很快找到最小步数，或者如油田问题，多少油田。
关于DFS，我们通过的是递归式的一步一步的根据我们的条件走，可以找到一条，这条路径被标记，得到结果后会回溯它，再找多条路径，对比最短路径。
京公网安备 11010502036488号