Description
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4) 找最短路挺好找，还原有点恶心了
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
int a[][];
const int INF=0x3f3f3f3f;
int dx[]={,,,-};
int dy[]={,-,,};
int d[][];
int sx,sy,gx,gy,nx,ny;
int res;
struct node
{
int x,y;
int prex,prey;
}path[][],tmp;
void bfs()
{
queue<node> q;
for(int i=;i<;i++){
for(int j=;j<;j++){
d[i][j]=INF;
}
}
path[sx][sy].x=sx;
path[sy][sy].y=sy;
q.push(path[sx][sy]);
d[sx][sy]=;
while(q.size()){
node p=q.front(),q.pop();
if(p.x==gx&&p.y==gy) break;
for(int i=;i<;i++){
nx=p.x+dx[i],ny=p.y+dy[i];
if(nx>=&&nx<&&ny>=&&ny<&&a[nx][ny]==&&d[nx][ny]==INF){
d[nx][ny]=d[p.x][p.y]+;
path[nx][ny].prex=p.x;
path[nx][ny].prey=p.y;
path[nx][ny].x=nx;
path[nx][ny].y=ny;
q.push(path[nx][ny]);
}
}
}
res=d[gx][gy];
}
void print_path(int x,int y)
{
if(x==&&y==){
cout<<"("<<path[][].x<<", "<<path[][].y<<")"<<endl;
return ;
}
nx=path[x][y].prex;
ny=path[x][y].prey;
print_path(nx,ny);
cout<<"("<<path[x][y].x<<", "<<path[x][y].y<<")"<<endl;
}
int main()
{
for(int i=;i<;i++){
for(int j=;j<;j++){
cin>>a[i][j];
}
}
sx=,sy=,gx=,gy=;
bfs();
print_path(,);
return ;
}
理解后自行敲一遍求总长的：
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
int dx[]={,,,-};
int dy[]={,-,,};
int a[][];
int sx,sy,gx,gy,nx,ny;
int d[][];
int res;
int bfs()
{
queue<P> que;
//P tmp; tmp.first=sx; tmp.second=sy; que.push(tmp);
que.push(P(sx,sy));//与上面的等价
//for(int i=0;i<5;i++){
// for(int j=0;j<5;j++){
// d[i][j]=INF;
// }
//}
memset(d,INF,sizeof(d));//与上面的等价 const int INF=0x3f3f3f3f;
//memset(d,0x3f3f,sizeof(d));//与上面的等价
sx=,sy=,gx=,gy=;//设置起点终点
d[sx][sy]=;
while(que.size()){
P q=que.front();
que.pop();
if(q.first==gx&&q.second==gy){
return d[gx][gy];//到终点停止循环并返回总长
}
for(int i=;i<;i++){
nx=q.first+dx[i],ny=q.second+dy[i];
if(nx>=&&nx<&&ny>=&&ny<&&a[nx][ny]==&&d[nx][ny]==INF){
d[nx][ny]=d[q.first][q.second]+;
que.push(P(nx,ny));
}
}
}
}
int main()
{
for(int i=;i<;i++){
for(int j=;j<;j++){
cin>>a[i][j];
}
}
cout<<bfs()<<endl;//输出最短的路径总长
return ;
}
菜鸡，2019/4/22再搞一遍带还原的。。。
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> S;
int a[][];
int d[][];
int sx=,sy=;
int gx=,gy=;
struct node
{
int first,second;
int prefirst,presecond;
}path[][],tmp;
int dx[]={,-,,};
int dy[]={,,,-};
int nx,ny;
int x,y;
int bfs()
{
memset(d,INF,sizeof(d));
queue<node> que;
path[][].first=sx,path[][].second=sy,path[][].prefirst=,path[][].presecond=;
que.push(path[][]);
d[path[][].first][path[][].second]=;
while(!que.empty()){
node k=que.front();
que.pop();
x=k.first,y=k.second;
if(x==gx&&y==gy) break;
for(int i=;i<;i++){
nx=x+dx[i],ny=y+dy[i];
if(nx>=&&nx<&&ny>=&&ny<&&a[nx][ny]!=&&d[nx][ny]==INF){
d[nx][ny]=d[x][y]+;
path[nx][ny].first=nx;
path[nx][ny].second=ny;
path[nx][ny].prefirst=x;
path[nx][ny].presecond=y;
que.push(path[nx][ny]);
}
}
}
return d[gx][gy];
}
void print_path(int x,int y)
{
if(x==&&y==){
cout<<"("<<path[][].first<<", "<<path[][].second<<")"<<endl;
return ;
}
nx=path[x][y].prefirst;
ny=path[x][y].presecond;
print_path(nx,ny);
cout<<"("<<path[x][y].first<<", "<<path[x][y].second<<")"<<endl;
}
int main()
{
for(int i=;i<;i++){
for(int j=;j<;j++){
cin>>a[i][j];
}
}
bfs();
print_path(,);
return ;
}