1.深度优先搜索
思路:以固定的移动顺序走迷宫,若能到终点则记一次
到终点后回溯到前一个有分岔的地方,走另一条路线
若走到死路也同样回溯到前一个有分叉的地方。
最终遍历所有路线
#include <bits/stdc++.h> using namespace std; int n,m,t,sx,sy,fx,fy,answer=0; int map1[10][10]; bool pass[10][10]; //计算顺序为 右、下、左、上 int ax[4]={1,0,-1,0}; int ay[4]={0,-1,0,1}; void dfs(int x,int y) { if(x==fx&&y==fy) { answer+=1; return; } for(int i=0;i<4;i++) { //移动后的x,y int xchange=x+ax[i]; int ychange=y+ay[i]; //同时满足:不超边界、不是障碍、不曾经过 if(xchange>0&&ychange>0&&xchange<=m&&ychange<=n&&map1[xchange][ychange]!=1&&pass[xchange][ychange]==0) { pass[xchange][ychange]=1;//点[xchange][ychange]已经经过 dfs(xchange,ychange);//下一步 pass[xchange][ychange]=0;//这一步之后的所有路径都被试过,往前回溯 } } }
所写函数dfs包括了移动一步,进行下一步和退回前一步三个操作
pass所记录的已经经过的位置是随路径的变化而变化的
接下来只要使用函数即可
int main() { cin>>n>>m>>t>>sx>>sy>>fx>>fy; //map中1为障碍 for(int i=0;i<t;i++) { int a,b; cin>>a>>b; map1[a][b]=1; } //经过起点 pass[sx][sy]=1; dfs(sx,sy); cout<<answer; return 0; }
2.广度优先搜索
思路:因为要考虑重复经过的问题,我们要求出经过某个点的最快路径就不能一条路走到底
因此要一步步走,将第一步能到的位置储存,再从第一步开始将第二步的所有位置储存
因为无法判定一共有多少步所以只能一步步走,因为无法移动到已经移动到的地方,所以最终会停止循环
根据这个特性可以开一个队列,先计算完步数小的后计算步数大的
#include <bits/stdc++.h> using namespace std; int n,m,x,y; int map1[450][450]; //8种走法 int ax[8]={-2,-1,1,2,2,1,-1,-2}; int ay[8]={1,2,2,1,-1,-2,-2,-1}; queue <pair<int,int> >q; void bfs() { while(q.empty()==false)//没有起始点后结束 { int x=q.front().first; int y=q.front().second; q.pop();//取出最前一组坐标为x,y并在队列中删除 for(int i=0;i<8;i++) { //移动后的x,y int xchange=x+ax[i]; int ychange=y+ay[i]; //同时满足:不超边界,不过重复点 if(xchange>0&&ychange>0&&xchange<=n&&ychange<=m&&map1[xchange][ychange]==-1) { q.push(make_pair(xchange,ychange));//重置起始点 map1[xchange][ychange]=map1[x][y]+1;//点[xchange][ychange]已经经过 } } } }
其中的bfs函数包括:取出要运算的坐标,移动,新增起始点 三个操作
只要是-1就表明还未经过,由此判断是否可以经过
最终处理后的map1就是要输出的结果
int main() { cin>>n>>m>>x>>y; //map初始化 for(int i=0;i<402;i++) { for(int j=0;j<402;j++) { map1[i][j]=-1; } } //经过起点 map1[x][y]=0;标签:10,sy,sx,int,题解,map1,&&,week4 From: https://www.cnblogs.com/if-I-can-fly/p/16902849.html
//将起点存入队列 q.push(make_pair(x,y)); bfs(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%-5d",map1[i][j]);//注意输出格式 } cout<<endl; } return 0; }