首页 > 代码库 > 迷宫问题
迷宫问题
迷宫问题通常是采用bfs方法去做，而且利用队列保存所访问过的但还未进行操作的点，从一个点出发将整个图遍历一遍，遍历过程中通过事先保存的用二维数组代表的方向，每次遍历每个方向
在迷宫问题中往往判断能否到达一个点，就是从你所要出发的点开始遍历，bfs完成后，去找那个点对应的visit值来进行判断
而在bfs过程中，往往可以利用fa[]数组来保存所连接的上一个点的位置，这个有助于我们找到最短路径，路上经过的每个点神马的
将未被访问的点进行入队列，并记上访问标志
这里介绍两种类型的迷宫问题
第一种是真正的迷宫：
往往使用数组 dir[4][2]={{1,-1},{-1,1},{1,1},{-1,-1}}代表可以行进的四个方向
题目大意：
从0,0开始找一条最短的路径到6,6，中间的障碍物是不能穿过的，问最短路径上的每个点，按顺序输出
1 #include<iostream> 2 #include<string.h> 3 #include<queue> 4 5 using namespace std; 6 7 int map[5][5]; 8 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 9 int visit[5][5]={0};10 int last[25];11 int ans[25];//用last得到的最短路径是倒置的，通过last再倒回来；12 13 struct Node{14 int x,y;15 int logo;16 }node[25];17 18 int main()19 {20 for(int i=0;i<5;i++)21 {22 for(int j=0;j<5;j++)23 {24 cin>>map[i][j];25 node[5*i+j].x=i;26 node[5*i+j].y=j;27 node[5*i+j].logo=map[i][j];28 }29 }30 31 queue<Node> Q;32 33 Q.push(node[0]);34 35 while(!Q.empty()){36 Node a=Q.front();37 visit[a.x][a.y]=1;38 //cout<<a.x<<‘\t‘<<a.y<<endl;39 Q.pop();40 for(int i=0;i<4;i++)41 {42 Node next;43 next.x=a.x+dir[i][0];44 next.y=a.y+dir[i][1];45 next.logo=node[5*next.x+next.y].logo;46 if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&next.logo==0&&visit[next.x][next.y]==0)47 {48 Q.push(next);49 last[next.x*5+next.y]=a.x*5+a.y;//last得到上一个节点的位置所在50 }51 }52 }53 54 int p=24,top=0;55 while(true)56 {57 ans[top++]=p;58 if(p==0) break;59 p=last[p];60 }61 62 while(top>0)63 {64 --top;65 cout<<"("<<ans[top]/5<<", "<<ans[top]%5<<")"<<endl;66 }67 68 return 0;69 }
第二题：
CSU 1224
下象棋上面，每个棋都有自己固定的走法，如我们这里对于马来说可以用数组
mov[8][2]={{2,1},{1,2},{-2,1},{1,-2},{2,-1},{-1,2},{-1,-2},{-2,-1}}来保存他的八种前进路径
来询问走最少几步可以吃掉将，我们通过马的点或者将的点开始遍历都是可以的，只要最后visit可以访问到就可以
用fa[]数组记录前一个节点，然后bfs结束后不断找前一个点直到找到为止，每找一次，次数加1得到步数
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 int mov[8][2]={{2,1},{1,2},{-2,1},{1,-2},{2,-1},{-1,2},{-1,-2},{-2,-1}}; 6 struct Node{ 7 int x, y; 8 }node[405]; 9 int visit[405],fa[405],n,m;10 queue<int> q;11 void bfs(int x,int y)12 {13 q.push((x-1)*n+y-1);14 while(!q.empty()){15 int u=q.front();q.pop();16 for(int i=0;i<8;i++){17 if(node[u].x+mov[i][0]<n&&node[u].x+mov[i][0]>=0&&node[u].y+mov[i][1]<m&&node[u].y+mov[i][1]>=0){18 int c=node[u].x+mov[i][0],d=node[u].y+mov[i][1];19 if(!visit[c*n+d]) {visit[c*n+d]=1;fa[c*n+d]=u;q.push(c*n+d);}20 }21 }22 }23 }24 int main()25 {26 int x,y,a,b;27 scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&a,&b);28 memset(visit,0,sizeof(visit));29 memset(fa,0,sizeof(fa));30 for(int i=0;i<n;i++)31 for(int j=0;j<m;j++)32 node[i*n+j].x=i,node[i*n+j].y=j;33 bfs(x,y);34 int c=(x-1)*n+y-1,d=(a-1)*n+b-1;35 int cnt=0;36 if(visit[c]){37 //while(c!=d) c=fa[c],cnt++;38 while(1){39 if(c==d) break;40 d=fa[d];41 cnt++;42 }43 printf("%d\n",cnt);44 }45 //while(fa1[a]!=x||fa2[b]!=y) a=fa1[a],b=fa2[b],cnt++;46 else puts("-1");47 return 0;48 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。