https://vjudge.net/problem/POJ-3984

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

 

用bfs,保存每一个点前面的点

wa的原因是x=pre[x][y][0];

y=pre[x][y][1];

有先后问题，就另设变量

#include<stdio.h>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int,int> p;
int a[6][6];
int pre[6][6][2];
int d[6][6];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int vis[6][6];
void bfs()
{
    d[1][1]=0;
    queue<p> que;
    p s;
    s.first=0;
    s.second=0;
    que.push(s);
    while(!que.empty())
    {
        p nw=que.front();
        que.pop();
        int x=nw.first;
        int y=nw.second;
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(!vis[tx][ty]&&a[tx][ty]==0&&tx>=0&&tx<=4&&ty>=0&&ty<=4)
            {
                vis[tx][ty]=1;
                pre[tx][ty][0]=x;
                pre[tx][ty][1]=y;

                p r;
                r.first=tx;
                r.second=ty;
                que.push(r);
            }
        }
    }
}
int main()
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
            scanf(" %1d",&a[i][j]);
    }
    bfs();
    int x=4,y=4;
    queue<p> ans;
    stack<p> s;
    while(1)
    {
   s.push(p(x,y));
     if(x==0&&y==0)
            break;
   int xx=x;
   int yy=y;
     x=pre[xx][yy][0];
     y=pre[xx][yy][1];


    }
      while(!s.empty())
      {
          p d=s.top();
          printf("(%d, %d)\n",d.first,d.second);
          s.pop();
      }
}