Sample Output
(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)这道题的难点在于状态的保存。用bfs是从最初的状态一直到最后状态，每一个状态都要保存前一个状态，这样才能保存路径，怎么保存状态呢？起初我想用链表，有点麻烦，所以用数组代替链表，就是开一个struct数组，记录当前节点编号，，和上一节点编号，根据编号找到上一个节点，这样子就在找到最短路径是从最后一个节点一直推会起点。#include<iostream>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>#define maxn 15#define inf 0x3f3f3f3fusing namespace std;int m,n;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int mp[maxn][maxn];bool vis[maxn][maxn];struct node{int x,y;int num;int last;node(int x=0,int y=0,int num=0,int last=0):x(x),y(y),num(num),last(last){};}pre[1005];bool judge(int x,int y){if(x>=0&&y>=0&&x<5&&y<5&&!vis[x][y]&&mp[x][y]==0)return true;return false;}node bfs(){ queue<node>q; int j=1; pre[1]=node(0,0,1,0); q.push(pre[1]); while(!q.empty()){node temp=q.front();q.pop();if(temp.x==4&&temp.y==4)return temp;for(int i=0;i<4;i++){int nx=temp.x+dir[i][0];int ny=temp.y+dir[i][1];if(judge(nx,ny)){vis[nx][ny]=1;j++;pre[j]=node(nx,ny,j,temp.num);q.push(pre[j]);}} }}stack<node> getpath(node a){stack<node>st; while(a.num!=NULL){st.push(a);a=pre[a.last]; } return st;}int main(){//freopen("in.txt","r",stdin);memset(vis,0,sizeof vis);for(int i=0;i<5;i++)for(int j=0;j<5;j++)scanf("%d",&mp[i][j]);node a=bfs();stack<node> b=getpath(a);while(!b.empty()){printf("(%d, %d)\n",b.top().x,b.top().y);b.pop();}}
找寻隐藏在山间的纯净和那“鸟鸣山更幽”的飞鸟。
