题意: 在 01 矩阵中, 找到一条从入口到终点的最短路径, 并且打印这条路径.
题目链接: http://lx.lanqiao.cn/problem.page?gpid=T291
- #include<iostream>
- #include<queue>
- #include<cstring>
- using namespace std;
- int vis[505][505];
- int map[505][505];
- int n,m;
- struct node{
- int x;
- int y;
- int dis; // 到达这个点的距离
- };
- queue<node>q;
- struct father{
- int x;
- int y;
- char dir; // 到达这个点的方式
- }path[505][505];
- bool judge(node nn)
- {
- if(nn.x<1||nn.x>n||nn.y<1||nn.y>m||map[nn.x][nn.y]==1||vis[nn.x][nn.y]==1)
- {
- return false;
- }
- return true;
- }
- char judge_dir(int k)
- {
- if(k==0)
- {
- return 'D';
- }
- if(k==1)
- {
- return 'L';
- }
- if(k==2)
- {
- return 'R';
- }
- if(k==3)
- {
- return 'U';
- }
- }
- int dx[4]={1,0,0,-1};// 下 (D), 左 (L), 右 (R), 上 (U)
- int dy[4]={0,-1,1,0};
- int bfs()
- {
- memset(vis,0,sizeof(vis));
- while(!q.empty())
- {
- q.pop();
- }
- node nn;
- nn.x=1;
- nn.y=1;
- nn.dis=0;
- vis[1][1]=1;
- q.push(nn);
- while(!q.empty())
- {
- node t=q.front();
- q.pop();
- for(int k=0;k<4;k++)
- {
- node next;
- next.x=t.x+dx[k];
- next.y=t.y+dy[k];
- next.dis=t.dis+1;
- if(judge(next))
- {
- //cout<<"next"<<next.x<<' '<<next.y<<endl;
- q.push(next);
- vis[next.x][next.y]=1;
- 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 -1;
- }
- void print_path(int xx,int yy)
- {
- if(xx==1&&yy==1)
- {
- return;
- }
- print_path(path[xx][yy].x,path[xx][yy].y);
- //cout<<"xx"<<xx<<endl;
- //cout<<"yy"<<yy<<endl;
- cout<<path[xx][yy].dir;
- }
- int main()
- {
- cin>>n>>m;
- getchar();
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- char ch=getchar();
- map[i][j]=ch-'0';
- }
- getchar();
- }
- int ans=bfs();
- cout<<ans<<endl;
- print_path(n,m);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2985419.html