#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;}
}