给定一个M行N列的迷宫图，其中 "0"表示可通路，"1"表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。
5行8列的迷宫如下：
0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0
则从左上角（1，1）至右下角（5，8）的最短路径为：
1,1--》2,1--》2,2--》2,3--》3,3--》3,4--》3,5--》4,5--》5,5--》5,6--》5,7--》5,8
题目保证每个迷宫最多只有一条最短路径。
请输出该条最短路径，如果不存在任何通路，则输出"NO FOUND".
输入格式:
第一行，输入M和N值，表示迷宫行数和列数。
接着输入M行数值，其中，0表示通路，1表示障碍物。每列数值用空格符间隔。
接下来可能输入多组迷宫数据。
当输入M的值为-1时结束输入。
输出格式:
按行顺序输出路径的每个位置的行数和列数，如 x,y
如果不存在任何路径，则输出"NO FOUND".
每组迷宫寻路结果用换行符间隔。
输入样例:
在这里给出一组迷宫。例如：
8 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4
0 0 1 0
0 0 0 0
0 0 1 1
0 1 0 0
-1 -1
输出样例:
在这里给出相应的输出。例如：1,1
2,1 3,1 4,1 5,1 5,2 5,3 6,3 6,4 6,5 7,5 8,5 8,6 8,7 8,8 NO FOUND
【抄同学的答案！满分】
#include <bits/stdc++.h> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ class node { public: int x,y; node() { } node(int ax,int ay) { x=ax; y=ay; } }; int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int vis[10005][10005]; int pre[10005][10005]; int main(int argc, char *argv[]) { int m,n; int aa=1; cin>>m>>n; while(m!=-1) { memset(vis,m*n,0); memset(pre,m*n,0); vector<vector<int> > v; for(int i=0;i<m;i++) { vector<int> t; v.push_back(t); for(int j=0;j<n;j++) { int ta; cin>>ta; v[i].push_back(ta); } } queue<node> q; q.push(node(0,0)); vis[0][0]=1; int f=0; while(!q.empty()) { node qf = q.front(); if(qf.x==m-1&&qf.y==n-1) { f=1; break; } q.pop(); for(int i=0;i<4;i++) { node tt(qf.x+mv[i][0],qf.y+mv[i][1]); if((tt.x>=0&&tt.x<m&&tt.y>=0&&tt.y<n)&&!vis[tt.x][tt.y]&&!v[tt.x][tt.y]) { vis[tt.x][tt.y] =1; pre[tt.x][tt.y] =qf.x*n+qf.y; q.push(tt); //cout<<tt.x<<" "<<tt.y<<endl; } } } if(f) { stack<node> sn; int xy = pre[m-1][n-1]; while(xy) { sn.push(node(xy/n+1,xy%n+1)); xy = pre[xy/n][xy%n]; } cout<<"1,1"<<endl; while(!sn.empty()) { cout<<sn.top().x<<","<<sn.top().y<<endl; sn.pop(); } cout<<m<<","<<n<<endl<<endl; }else { cout<<"NO FOUND"<<endl; } cin>>m>>n; } return 0; }
【自己写的】
#include <iostream> #include <string.h> using namespace std; /* *迷宫最短路径 *迷宫数组是从1 开始 */ int n,m,p,q,Min=9999;//迷宫n行m列，出口位置(p,q) int a[51][51]={0};//迷宫数组 int book[51][51]={0};//标记是否走过 int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//向下，向右，向上，向左 int stepA[100][2]={-1};//记录当前路径 int stepB[100][2]={-1};//记录最小路径 void dfs(int x,int y,int step) { int tx,ty,k; if(x==p&&y==q) { if(step<Min) { for(int t=0;t<100;t++) { if(stepA[t][0]==-1&&stepA[t][1]==-1) { break; } stepB[t][0]=stepA[t][0]; stepB[t][1]=stepA[t][1]; } Min=step; } return; } for(k=0;k<=3;k++) { //计算下一点的坐标 tx=x+next[k][0]; ty=y+next[k][1]; if(tx<1||tx>n||ty<1||ty>m) continue; if(a[tx][ty]==0&&book[tx][ty]==0) { stepA[step][0]=tx; stepA[step][1]=ty; book[tx][ty]=1;//标记已经走过了这个点 dfs(tx,ty,step+1);//尝试下一个点 book[tx][ty]=0;//取消这个点的标记 } } return; } int main() { int startx=0,starty=0; cout<<"请输入迷宫的大小(行、列):"<<endl; cin>>n>>m; cout<<"请输入迷宫布局('0'代表通路,'1'代表墙):"<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } cout<<"请输入起点与终点坐标：" <<endl; cin>>startx>>starty>>p>>q; book[startx][starty]=1; dfs(startx,starty,0); if(Min==9999)//没有最短路径就说明没有通路 { cout<<' '<<"【提示】两点之间没有通路！"<<endl; return 0; } cout<<"走出迷宫最少步数："<<endl; cout<<Min<<endl; cout<<"迷宫最短路径："<<endl; for(int t=0;t<Min;t++) { if(t==0) cout<< startx<<" "<<starty<<endl; cout<<stepB[t][0]<<" "<<stepB[t][1]<<endl; } return 0; }
代码截图：【帅不帅气，一给我里giaogiao】
