OJ 4127:迷宫问题 递归输出路径

描述

定义一个二维数组： 

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

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

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

#include <iostream>
#include "cstring"
#include <stdio.h>
#include "iomanip"
#include "vector"
#include "cmath"
#include "stack"
#include "algorithm"
#include <math.h>
#include "map"
#include "queue"
struct node {
int x,y;
int step;
node (){}
node (int xx,int yy ,int stepp)
{
    x=xx;
    y=yy;
    step=stepp;
}
};
void prri(node n[100][100],int x,int y)
{
    if(x==0&&y==0)
    {


        return;
    }

     prri(n,n[x][y].x,n[x][y].y);
    printf("(%d, %d)\n",n[x][y].x,n[x][y].y);

}
using namespace std;
int main()
{
    freopen("a.txt","r",stdin   );
    int r,c;
    r=5;c=5;
    int  visit[100][100]={0};
    node nn[100][100];
    nn[0][0].x=0;
    nn[0][0].y=0;
int a[100][100]={0};

    int min=3232323;
    for(int i=0;i<r;i++)
       {

           for(int j=0;j<c;j++)
           {
               cin>>a[i][j];
           }
       }
       queue <node> q;
       node t=node(0,0,1);
       q.push(t);

       while(!q.empty())
       {
            t=q.front();
            q.pop();
           int rx,ry,rstep;
           rx=t.x;
           ry=t.y;
           rstep=t.step;
           if(rx==r-1&&ry==c-1)
           {
//               cout<<rstep;
               break;
           }

           if(visit[rx][ry]==1)
            continue;
           visit[rx][ry]=1;
           for(int x=0;x<r;x++)
            for(int y=0;y<c;y++)
           {
               if(x==rx&&y==ry)
                continue;
               if((x==rx-1&&y==ry)||(x==rx+1&&y==ry))
               {
                    if(a[x][y]==0&&visit[x][y]==0)
                    {
                        nn[x][y].x=rx;
                        nn[x][y].y=ry;
                        t=node(x,y,rstep+1);
                        q.push(t);

                    }
               }
                if((x==rx &&y==ry-1)||(x==rx&&y==ry+1))
               {
                    if(a[x][y]==0&&visit[x][y]==0)
                    {
                        nn[x][y].x=rx;
                        nn[x][y].y=ry;
                        t=node(x,y,rstep+1);
                        q.push(t);

                    }
               }



           }
       }
       prri(nn ,4,4);
        cout<<"(4, 4)";
    return 0;
}