-->
题意：在01矩阵中，找到一条从入口到终点的最短路径，并且打印这条路径。
题目链接：http://www.sychzs.cn/www.sychzs.cn?gpid=T291
#include
#include
#include
using namespace std;
int vis[][];
int map[][];
int n,m;
struct node{
int x;
int y;
int dis; //到达这个点的距离
};
queueq;
struct father{
int x;
int y;
char dir; //到达这个点的方式
}path[][];
bool judge(node nn)
{
if(nn.x<||nn.x>n||nn.y<||nn.y>m||map[nn.x][nn.y]==||vis[nn.x][nn.y]==)
{
return false;
}
return true;
}
char judge_dir(int k)
{
if(k==)
{
return 'D';
}
if(k==)
{
return 'L';
}
if(k==)
{
return 'R';
}
if(k==)
{
return 'U';
}
}
int dx[]={,,,-};//下（D），左（L），右（R），上（U）
int dy[]={,-,,};
int bfs()
{
memset(vis,,sizeof(vis));
while(!q.empty())
{
q.pop();
}
node nn;
nn.x=;
nn.y=;
nn.dis=;
vis[][]=;
q.push(nn);
while(!q.empty())
{
node t=q.front();
q.pop();
for(int k=;k<;k++)
{
node next;
next.x=t.x+dx[k];
next.y=t.y+dy[k];
next.dis=t.dis+;
if(judge(next))
{
//cout<<"next "<
q.push(next);
vis[next.x][next.y]=;
path[next.x][next.y].x=t.x;
path[next.x][next.y].y=t.y;
path[next.x][next.y].dir=judge_dir(k);
if(next.x==n&&next.y==m)
{
return next.dis;
}
}
}
}
return -;
}
void print_path(int xx,int yy)
{
if(xx==&&yy==)
{
return;
}
print_path(path[xx][yy].x,path[xx][yy].y);
//cout<<"xx"<
//cout<<"yy"<
cout<
{
cin>>n>>m;
getchar();
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
char ch=getchar();
map[i][j]=ch-'';
}
getchar();
}
int ans=bfs();
cout<
print_path(n,m);
return ;
}
-->
