미궁

#include <iostream>

#include <string>

using namespace std;



const int N=100;

const int M=100;



typedef struct   //      

{

    char c;

    short int p_row,p_col,step;

}Maze;

Maze a[N][M];



bool pathed[N][M]; //      

short int p[4][2]={-1,0,0,1,1,0,0,-1};//      

int n,m;//    

int bfs(int,int);



typedef struct //      

{

    int row,col,step;

} queue_type;

queue_type queue[N*M];



void bfs(int n,int m,int b_i,int b_j,int e_i,int e_j)

{

    memset(pathed,0,sizeof(pathed));//        



    int row,col,start=0,end=1,;//       

    queue[start].row=b_i, queue[start].col=b_j, queue[start].step=a[b_i][b_j].step=0; //       

    pathed[b_i][b_j]=1;            //    



    while (start<end)

    {

        for (int i=0;i<4;i++)

        {

            row=queue[start].row+p[i][0],col=queue[start].col+p[i][1];

            if (row>=0 && row<n && col>=0 && col<m && pathed[row][col]==0 && a[row][col].c!='#')

            {

                pathed[row][col]=1;                 //    

                queue[end].row=row,queue[end].col=col,queue[end].step=queue[start].step+1;  //       



                a[row][col].step=queue[end].step;   //    

                a[row][col].p_row=queue[start].row,a[row][col].p_col=queue[start].col; //     

                end++;

                if (row==e_i && col==e_j)  //       ，  

                    return;

            }

        }

        start++;

    }

}



void out_path(int b_i,int b_j,int e_i,int e_j)

{

    if (e_i==b_i && e_j==b_j)

    {

        printf("(%d,%d)",b_i,b_j);

        return ;

    }

    else

        out_path(b_i,b_j,a[e_i][e_j].p_row,a[e_i][e_j].p_col);

    printf("-->(%d,%d)",e_i,e_j);

}



int main()

{

    int i,j,n,m,b_row,b_col,e_row,e_col;

    cout<<"    、  "<<endl;

    cin>>n>>m;

    cout<<"    "<<endl;

    for (i=0;i<n;i++)

        for (j=0;j<m;j++)

        {

            cin>>a[i][j].c;

            a[i][j].step=-1;

        }



    cout<<"      "<<endl;

    cin>>b_row>>b_col;

    cout<<"      "<<endl;

    cin>>e_row>>e_col;

    bfs(n,m,b_row,b_col,e_row,e_col);

    for (i=0;i<n;i++)

    {

        cout<<endl;

        for (j=0;j<n;j++)

            printf("%4d",a[i][j].step);

    }

    cout<<endl<<endl;

    if (a[e_row][e_col].step==-1)

        cout<<"No path!"<<endl;

    else

    {

        out_path(b_row,b_col,e_row,e_col);

        cout<<endl;

    }

}