|
题目的大致意思是：给你一个5*5的迷宫，然后你只能往上，下，左，右四个方向走，然后0代表的是可以走的路，1代表的是墙不可以走。然后让我们求出从左上角到右下角的最短路线及其长度。
求长度是好做的，但是输出路径这个我还是第一次碰到。
这里我们使用的队列不可以是STL中的queue了，要用数组来写，因为我们在这里需要头尾两个指针。
然后我们这里还要用到一个保存前驱节点的数组pre，这样在我们输出路径的时候就可以回溯上去。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define maxn 7
int vis[maxn][maxn],a[maxn][maxn],pre[33];
int N,K;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct node{
int x,y;
}que[33];
void print(int head){
int t=pre[head];
if(t==-1){
printf("(0, 0)\n");
//printf("(%d, %d)\n",que[head].x,que[head].y);
return ;
}
print(t);
printf("(%d, %d)\n",que[head].x,que[head].y);
}
void bfs(){
int head=0;
int tail=0;
que[tail].x=0;
que[tail].y=0;
pre[tail]=-1;
tail++;
while(head<tail){
int x=que[head].x;
int y=que[head].y;
if(x==4&&y==4){
//printf("%d\n",head);
print(head);
return ;
}
for(int i=0;i<3;i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<0||ty<0||tx>4||ty>4||vis[tx][ty]||a[tx][ty]) continue;
que[tail].x=tx;
que[tail].y=ty;
pre[tail]=head;
vis[tx][ty]=1;
tail++;
}
head++;
}
}
int main(){
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&a[i][j]);
vis[0][0]=1;
bfs();
}
| 
转播
