简单的迷宫问题
- 题目描述
- 输入样例
- 输出样例
- dfs解题思路(深搜)
- 路线规划
- DFS特点
- C++源码(DFS)
- bfs解题思路(广搜)
- 路线规划
- 测试代码段
- BFS特点
- C++源码（BFS）
题目描述
现在需要你来规划一条路线，从起点到终点的最短路线。
给你一个n×m的地图（0<n<100,0<m<100），再给你一个起点和终点的坐标，你来判断一下从起点到终点的最短路线mini需要走多少。
输入样例
6 4
1 1 1 1
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
0 0
4 2
输出样例
8
dfs解题思路(深搜)
路线规划
红色为第一次寻找线路，绿色为回溯线路，蓝色、黄色、紫色则是根据上下左右四个方向的优先级从不同路线进行尝试，最终将每一条路径的长度都与最小值进行判断，以此寻找最短路径的长度。
1.利用方向数组、标记数组分别经行行走方向的判断与路线的判断
2.回溯法：以每一步节点为起点，逐条线路进行遍历
DFS特点
空间复杂度较低，时间复杂度较高，牺牲时间省内存
C++源码(DFS)
#include<iostream>
using namespace std;int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; ///方向数组
bool mark[105][105]; ///标记数组
int Map[105][105]; ///地图
int m,n,startx,starty,p,q,mini=99999; ///题目要求数据/最短路径void dfs(int x,int y,int step)
{mark[x][y] = true; ///标记该位置为已走过if(x == p && y == q) ///递归出口{if(step<mini)mini=step;return ;}for(int i=0;i<4;i++) ///四个方向进行遍历{int x1 = x + dir[i][0];int y1 = y + dir[i][1];if(x1>=0 && y1>=0 && x1<n && y1<m && Map[x1][y1] == 1 && !mark[x1][y1]) ///判断是否能走{mark[x1][y1]=true; ///标记为已走过dfs(x1,y1,step+1); ///下一步mark[x1][y1]=false; ///回溯}}return ;
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>Map[i][j];cin>>startx>>starty;cin>>p>>q;dfs(startx,starty,0); ///从起始点开始走if(mini==99999) ///输出最短路径长度或sorrycout<<"sorry"<<endl;elsecout<<mini<<endl;return 0;
}bfs解题思路(广搜)
路线规划
红色为可以到达终点的一条线路，也是最短线路之一
测试代码段
将以下代码插入到源码中对应位置，每走一步输出一次地图
…… ……
//if(Map[x1][y1] == 1 && !mark[x1][y1]) ///判断是否能走
//{
///程序每走一步，输出一遍地图，当前位置为#，通俗易懂for(int i1=0; i1<n; i1++){for(int j1=0; j1<m; j1++){if(i1 == x1 && j1 == y1)cout<<"#"<<" ";elsecout<<Map[i1][j1]<<" ";}cout<<endl;}Sleep(1000);///延时1ssystem("cls");//node s;//s.x=x1;//s.y=y1;//s.step=step+1; ///步数+1//f.push(s); ///入队完毕//mark[x1][y1]=true; ///访问过此点
//}…… ……
BFS特点
时间复杂度较低，空间复杂度较高，牺牲内存省时间
C++源码（BFS）
#include<bits/stdc++.h>
#include<iostream>
#include<queue> ///队列头文件
using namespace std;int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; ///方向数组
int Map[105][105]; ///地图
bool mark[105][105]; ///标记数组
int m,n,startx,starty,p,q,T=0; ///题目所需数据/到达终点标记struct node ///定义结构体(存放(x,y)坐标与当前步数)
{int x,y;int step;
} start;queue <node> f; ///定义结构体队列void bfs()
{start.x=startx;start.y=starty;start.step=0;f.push(start); ///将起点入队while(!f.empty()) ///while(!f.empty())判断队列是否为空{int x=f.front().x;int y=f.front().y;int step=f.front().step;if(x == p && y== q) ///如果是终点输出(一定为最短路径){cout<<step<<endl;T=1; ///标记到达了终点return;}for(int i=0; i<4; i++) ///向四个方向遍历{int x1=x+dir[i][0];int y1=y+dir[i][1];if(Map[x1][y1] == 1 && !mark[x1][y1]) ///判断是否能走{node s;s.x=x1;s.y=y1;s.step=step+1; ///步数+1f.push(s); ///入队完毕mark[x1][y1]=true; ///访问过此点}}f.pop(); ///出队}
}
int main()
{cin>>n>>m;for(int i=0; i<n; i++)for(int j=0; j<m; j++)cin>>Map[i][j];cin>>startx>>starty;cin>>p>>q;mark[startx][starty]=true; ///将起点标记bfs();if(T == 0) ///是否能到达终点cout<<"sorry"<<endl; ///不能到达输出"sorry"return 0;
}
