给定一个M行N列的迷宫图，其中 "0"表示可通路，"1"表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。
5行8列的迷宫如下：
则从左上角（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
,
,
,
,
,
,
,
,
,
,
,
,
,
, 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[][]={{,},{,-},{,},{-,}};
int vis[][];
int pre[][];
int main(int argc, char *argv[]) {
int m,n;
int aa=;
cin>>m>>n;
while(m!=-)
{
memset(vis,m*n,);
memset(pre,m*n,);
vector<vector<int> > v;
for(int i=;i<m;i++)
{
vector<int> t;
v.push_back(t);
for(int j=;j<n;j++)
{
int ta;
cin>>ta;
v[i].push_back(ta);
}
} queue<node> q;
q.push(node(,));
vis[][]=;
int f=;
while(!q.empty())
{
node qf = q.front();
if(qf.x==m-&&qf.y==n-)
{
f=; break; }
q.pop();
for(int i=;i<;i++)
{
node tt(qf.x+mv[i][],qf.y+mv[i][]);
if((tt.x>=&&tt.x<m&&tt.y>=&&tt.y<n)&&!vis[tt.x][tt.y]&&!v[tt.x][tt.y])
{
vis[tt.x][tt.y] =;
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-][n-];
while(xy)
{ sn.push(node(xy/n+,xy%n+));
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 ;
}
【献给那些努力奋斗的同学儿，努力学习为国争光！】
#include <iostream>
#include <string.h>
using namespace std;
/*
*迷宫最短路径
*迷宫数组是从1 开始
*/
int n,m,p,q,Min=;//迷宫n行m列，出口位置(p,q)
int a[][]={};//迷宫数组
int book[][]={};//标记是否走过
int next[][]={{,},{,},{,-},{-,}};//向下，向右，向上，向左 int stepA[][]={-};//记录当前路径
int stepB[][]={-};//记录最小路径 void dfs(int x,int y,int step)
{
int tx,ty,k;
if(x==p&&y==q)
{
if(step<Min)
{
for(int t=;t<;t++)
{
if(stepA[t][]==-&&stepA[t][]==-)
{
break;
}
stepB[t][]=stepA[t][];
stepB[t][]=stepA[t][];
} Min=step;
}
return;
} for(k=;k<=;k++)
{
//计算下一点的坐标
tx=x+next[k][];
ty=y+next[k][];
if(tx<||tx>n||ty<||ty>m)
continue; if(a[tx][ty]==&&book[tx][ty]==)
{
stepA[step][]=tx;
stepA[step][]=ty; book[tx][ty]=;//标记已经走过了这个点
dfs(tx,ty,step+);//尝试下一个点
book[tx][ty]=;//取消这个点的标记
}
}
return;
}
int main()
{
int startx=,starty=;
cout<<"请输入迷宫的大小(行、列):"<<endl;
cin>>n>>m;
cout<<"请输入迷宫布局('0'代表通路,'1'代表墙):"<<endl;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>a[i][j];
}
}
cout<<"请输入起点与终点坐标：" <<endl;
cin>>startx>>starty>>p>>q;
book[startx][starty]=;
dfs(startx,starty,);
if(Min==)//没有最短路径就说明没有通路
{
cout<<'\n'<<"【提示】两点之间没有通路！"<<endl;
return ;
}
cout<<"走出迷宫最少步数："<<endl;
cout<<Min<<endl;
cout<<"迷宫最短路径："<<endl;
for(int t=;t<Min;t++)
{
if(t==)
cout<< startx<<" "<<starty<<endl;
cout<<stepB[t][]<<" "<<stepB[t][]<<endl; }
return ;
}
代码截图：【帅不帅气，一给我里giaogiao】