1.走迷宫

描述

有一个N*M(N,M<=10)的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，人在迷宫中可以尝试上下左右四个方向移动。另外，在迷宫中如果从左边走出迷宫会回到迷宫最右边一格（只要该格不是墙），行不变，同样，从右边走出迷宫会回到迷宫最左边一格，向上走出迷宫会回到迷宫最下边一格，向下走出迷宫会回到迷宫最上边一格。现在给定一个迷宫，以及起点和终点，问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式

该程序为多CASE，第1行为CASE的数量
每一个CASE，第1行为两个数N（行）和M（列）
然后N行每行M个数，之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

题意&&思路：

普通bfs,如果左边是0，最右边没有墙的话，可以往左走走到最右边。
如果右边是n，最左边没有墙的话，可以往右走走到最走边
如果上面是0，最下面没有墙的话，可以往上走走到最下面。
,如果下面是m，最上边没有墙的话，可以往下走走到最上面。

Input

2
4 3
011
010
110
110
0 0 3 2
2 2
01
10
0 0 1 1

Output

4
die

潇洒哥的AC代码（卓佬）

#include <stdio.h> #include <queue> using namespace std; typedef struct { int r,c,s; }loc; int sr,sc,dr,dc; int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; char d[100][100]; void bfs() { int m,n,i,j,nr,nc;     loc first,cur,next;     queue<loc>que; scanf("%d%d",&m,&n); //读入m行的迷宫矩阵数据，存放在d数组中 for(int i=0; i<m; i++) { scanf("%s",d[i]); } //读入起始位置的行列值（sr,sc）和终止位置的行列值（dr,dc） scanf("%d%d%d%d",&sr,&sc,&dr,&dc); if(sr==dr&&sc==dc) { printf("0n"); return; }     first.r=sr,first.c=sc,first.s=0;     que.push(first); while(!que.empty()) { //取出队列头元素，存入cur         cur=que.front();         que.pop(); //弹出队列头元素 if(cur.r==dr&&cur.c==dc) { printf("%dn",cur.s); return; } for(i=0; i<4; i++) {             nr=cur.r+dir[i][0];             nc=cur.c+dir[i][1];             nr=(nr+m)%m;//%%%%%%卓佬的%%tql，orz             nc=(nc+n)%n;//%%%%%% if(d[nr][nc]=='0') {                 next.r=nr;                 next.c=nc;                 next.s=cur.s+1;                 que.push(next);                 d[nr][nc]='1'; } } } printf("dien"); } int main() { int n; scanf("%d",&n); while(n--) bfs(); }

AC(前排让给卓佬)

#include <iostream> #include <queue> #include <cstring> using namespace std; char g[100][100]; int sx,sy,ex,ey, vis[100][100]; int n,m; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; struct point { int x,y,s; }; void bfs() { if(sx==ex&&sy==ey) {         cout<<0<<endl; return; }     queue<point>q;     point first={sx,sy,0};     vis[sx][sy]=1;     q.push(first); int flag=0; int ans=0; while(!q.empty()) {         point temp=q.front();         q.pop(); if(temp.x==ex&&temp.y==ey) {             flag=1;             ans=temp.s; break; } for(int i=0; i<4; i++) {             point next; int tx=temp.x+dx[i]; int ty=temp.y+dy[i]; if(tx<0)tx=n-1; if(tx>=n)tx=0; if(ty<0)ty=m-1; if(ty>=m)ty=0; if(!vis[tx][ty]&&g[tx][ty]=='0') {                 next={tx,ty,temp.s+1};                 q.push(next);                 vis[tx][ty]=1; } } } if(flag)cout<<ans<<endl; else cout<<"die"<<endl; } int main() {     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t;     cin>>t; while(t--) { memset(vis, 0, sizeof(vis));         cin>>n>>m; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) {                 cin>>g[i][j]; } }         cin>>sx>>sy>>ex>>ey; bfs(); } return 0; } 

2：走迷宫（带传送门，加强版）

题意：

有一个N*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中
有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试
上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点，
问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

Input

该程序为多CASE，第1行为CASE的数量
每一个CASE，第1行为两个数N（行）和M（列）
然后N行每行M个数
之后是一个数W，为传送门的数量
之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2
之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)
注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置
所有数字不超过100

Output

如题

Sample Input

2
4 3
011
011
110
110
1
1 0 2 2
0 0 3 2
2 2
01
10
0
0 0 1 1

Sample Output

3
die

题意：

如果只是单纯的走迷宫直接bfs即可，可本题加多了传送门还是bfs x
（如果是传送门无非就是换了个地方bfs）
每走一步，要看一下当前节点是否有传送门，
本题主要是如何把 存传送门的数组 和 存迷宫的g[x][y] 建立联系。其实用一个数组去存传送门的坐标即可
“注意”：

1. 如果在传送门的位置 不能往四个方向移动，可以写if，然后break，掉。
2. 对于不是传送门的点 和普通走迷宫的判断相同。
3. 对于是传送门的点直接改变vis数组，并入队即可（为什么这里直接入队，和2不同，
   （因为：
   1：走传送门可能把你传回迷宫起点附近，而假如是这种情况的话，由于前面已经进行了bfs，前面点的vis【】【】已被标记，故已经是最短路，再回去已经不用更新数组了（在更新肯定更大了）(距离是相对的 )
   2假如传送门把你传到了相对迷宫终点更近的地方，那么入队，进行bfs。对传送门终点进行所在树的那一层 bfs。）

下面按照不同数据规模给出标程

掌握->了解->知道

AC代码（zzx，解决本道题用这个代码即可，因为数据量小）

#include <iostream> using namespace std; /**< 有一个N*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中 有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试 上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点， 问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。 */ /**< 该程序为多CASE，第1行为CASE的数量 每一个CASE，第1行为两个数N（行）和M（列） 然后N行每行M个数 之后是一个数W，为传送门的数量 之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2 之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)  注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置 所有数字不超过100 */ int T,N,M,W,c1[105],r1[105],c2[105],r2[105],sc,sr,ec,er; char a[105][105]; int v[105][105]; int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0}; struct node { int x,y; }; void bfs(int x,int y) {     node q[10005]; int i,j,f=0,r=0;     v[x][y]=1;     q[r++]= {x,y}; while(f!=r) {         node tem=q[f++]; if(tem.x==ec&&tem.y==er)//判断是否在终点 break; for(j=0; j<W; j++)//判断所在位置是否有传送门 { if(tem.x==c1[j]&&tem.y==r1[j])//找到 break; } if(j!=W)//如果传送门的出口能走 {             q[r++]= {c2[j],r2[j]};//走             v[c2[j]][r2[j]]=v[tem.x][tem.y]+1; } else//如果该位置没有传送门 { for(i=0; i<4; i++)//四个方向都走走 { int cx=tem.x+dx[i],cy=tem.y+dy[i]; if(cx>=0&&cx<N&&cy>=0&&cy<M&&a[cx][cy]=='0'&&v[cx][cy]==0)//如果能走，走 {                      q[r++]= {cx,cy};//入队                     v[cx][cy]=v[tem.x][tem.y]+1; } } } } } int main() { int i,j,k;     cin>>T; while(T--) {         cin>>N>>M; for(i=0; i<N; i++) { for(j=0; j<M; j++) {                 cin>>a[i][j]; } }         cin>>W; for(k=0; k<W; k++) {             cin>>c1[k]>>r1[k]>>c2[k]>>r2[k]; }         cin>>sc>>sr>>ec>>er; bfs(sc,sr); if(v[ec][er]!=0)             cout << v[ec][er]-1 << endl; else             cout<<"die"<<endl; } return 0; }

预备知识

对于第二种标程先普及下stl中的queue
本文用到了以下函数

1. **头文件 #inclue< queue > **
2. 初始化: queue< point >q <>里放的是队列元素的数据类型，本题即是point，里面加x，y，step。
3. 队列函数：q.front()读取队首元素
4. q.pop()把队首元素出队
5. q.push()把元素进队尾
6. point t={x,y,step}结构体赋值

AC 代码（chp的，用数组存储传送门，用的时候直接调用即可+stl）

（ 有很多传送门时的操作，直接像做法一可能超时，这里引进，数组存储传送门）

用了数组存储传送门的地方已标记出，还有运用了stl的地方，

//      BFS #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int N = 110; int map[N][N]; bool vis[N][N]; struct node { int x,y,id; }csm[N][N]; struct node1 { int x,y,step; }; int nx[4]={0,0,1,-1},ny[4]={1,-1,0,0}; int ans,n,m,ex,ey,sx,sy; void bfs() {     queue<node1> q;     node1 a,next;     a.x=sx;     a.y=sy;     a.step=0;     q.push(a);     vis[sx][sy]=true; while(!q.empty()) {         a=q.front();         q.pop(); int x=a.x,y=a.y; if(x==ex&&y==ey) {             ans=a.step; return ; } if(csm[x][y].id) {             next.x=csm[x][y].x;             next.y=csm[x][y].y;             next.step=a.step+1;             q.push(next);             vis[next.x][next.y]=true; } else { for(int i=0;i<4;i++) {                 x=a.x+nx[i],y=a.y+ny[i]; if(map[x][y]||x<0||y<0||x>=n||y>=m||vis[x][y]) { continue; }                 next.x=x;                 next.y=y;                 next.step=a.step+1;                 q.push(next);                 vis[x][y]=true; } } } } int main() { int t; scanf("%d",&t); while(t--) { memset(vis,false,sizeof(vis)); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) {                 csm[i][j].id=0; } } scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%1d",&map[i][j]); } } int k; scanf("%d",&k); for(int i=1;i<=k;i++) { int a,b,c,d;//存传送门的地方 scanf("%d%d%d%d",&a,&b,&c,&d);             csm[a][b].x=c;             csm[a][b].y=d;             csm[a][b].id=1; } scanf("%d%d%d%d",&sx,&sy,&ex,&ey); int inf=0x3f3f3f3f;         ans=inf; bfs(); if(ans==inf) { printf("dien"); } else printf("%dn",ans); } return 0; }

最后是博主的代码（博主太菜了，所以放最后面，前排让给大哥）

我开了一个五方向 数组。后面判断时用逻辑或不要位运算或，10wa血淋淋的教训qwq。

#include <iostream> #include <cstring> #include <queue> using namespace std; const int maxn=1e2+10; struct point { int x,y;//入队时的坐标 }; struct ch { int xs,ys;//传送门的起点和终点 int xe,ye; } c[maxn];// 放传送门的数组，即传送门的数据结构 char g[maxn][maxn];//存放maze int vis[maxn][maxn],vc[maxn][maxn], n, m,xs,ys,xe,ye; //xs，ys出发点，xe，ye终点。 //我的vis用来存：从起点到这个点的最小距离（因为有传送门所以要判断是否更新vis） //vc我用来存输入的传送门的编号，以便倒时判断是否要传送。 int dx[5]= {0,0,0,1,-1};//方向 int dy[5]= {0,1,-1,0,0}; //其实后面敲完后发现可以直接把方向定位dx 【5】 //0，0表示是否可以进入传送门 void bfs() {     queue<point>q; int flag=0;//判断是否能走出maze。flag=1走得出迷宫     vis[xs][ys]=1;     point tmp= {xs,ys};//起点入队 //坑点！！！！！！！！ //假如起点是传送门，直接开始传送！！！！！ //过了一次后，我这里之前开的是方向是四维，之后改成了5维，可以少写点码。     q.push(tmp); while(!q.empty()) {         tmp=q.front(),q.pop(); if(tmp.x==xe&&tmp.y==ye) {             flag=1;//可以走出迷宫 break;//找到终点，走出迷宫，结束bfs } for(int i=0; i<5; i++)//方向数组的遍历 { int tx=tmp.x+dx[i]; int ty=tmp.y+dy[i];             point t2;//设定一个临时变量t1（x，y） //vis[tx][ty]=vis[tmp.x][tmp.y]+(dx[i]|dy[i]);//有两种情况：这个节点本身就是传送门的入口 //（dx[i]|dy[i]）这一步当且仅当dx=0和dy=0时；(dx[i]|dy[i])才为0 //由（tmp.x，tmp.y）到（tx，ty）可能走0步（即本身是传送门的情况）。 //另外一种是这个节点往四个方向走，可能存在传送门， if(tx>=0&&tx<n&&ty>=0&&ty<m&&vc[tx][ty])//vc[tx][ty]表示是否有这个传送门的编号（1~w） {                 vis[tx][ty]=vis[tmp.x][tmp.y]+(dx[i]||dy[i]); int id=vc[tx][ty];//读取传送门的编号（第几个），之后根据编号，去找到对应的传送门 //t2.x=c[id].xe;//存传送门终点的坐标 //t2.y=c[id].ye;                 t2={c[id].xe,c[id].ye};//结构体赋值                 vis[t2.x][t2.y]=vis[tx][ty]+1;//走传送门                 q.push(t2);//把传送门的终点入队。 if(dx[i]==0&&dy[i]==0)//如果节点走都没走，直接就是传送门，那么就break，下面肯定没有关于这个节点的四个方向。 { break; } } else if(tx>=0&&tx<n&&ty>=0&&ty<m&&g[tx][ty]!='1'&&!vis[tx][ty])//这点不是传送门 {                 vis[tx][ty]=vis[tmp.x][tmp.y]+(dx[i]||dy[i]);                 t2= {tx,ty}; //结构体赋值                 q.push(t2); } } } if(!flag)cout<<"die"<<endl; else cout<<vis[xe][ye]-1<<endl; } int main() { int t;     cin>>t; while(t--) { memset(vis,0,sizeof(vis)); memset(vc,0,sizeof(vc));//多case每次都要初始化         cin>>n>>m; for(int i=0; i<n; i++) for(int j=0; j<m; j++)cin>>g[i][j]; int w;         cin>>w; for(int i=1; i<=w; i++) {             cin>>c[i].xs>>c[i].ys>>c[i].xe>>c[i].ye;//输入传送门的坐标             vc[c[i].xs][c[i].ys]=i;//通过传送门的起点来保存 //vc【x】【y】=i---第几个传送门 }         cin>>xs>>ys>>xe>>ye; bfs(); } return 0; }