Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define FOR(i,a,b) for(int i=a;i<b;i++)
- #define For(i,b) FOR(i,0,b)
- #define pi pair<int,int>
- #define f first
- #define s second
- const int MX=105;
- int grid[MX][MX];
- int dist[MX][MX];
- int from[MX][MX];
- int dx[4]={1,-1,0,0};
- int dy[4]={0,0,1,-1};
- char dir[4]={'U','D','L','R'};//opposite of dx,dy
- int main(){
- int n,m;cin>>n>>m;
- int sx,sy,fx,fy;
- For(i,n){
- string S;cin>>S;
- For(j,m){
- if(S[j]=='#')grid[i][j]=0;
- else grid[i][j]=1;
- if(S[j]=='S')sx=i,sy=j;
- if(S[j]=='F')fx=i,fy=j;
- }
- }
- For(i,n)For(j,m)dist[i][j]=1e9;
- //BFS from end point
- queue<pi> q;
- q.push({fx,fy});
- dist[fx][fy]=0;
- while((int)q.size()){
- pi x=q.front();q.pop();
- For(k,4){
- int nx=x.f+dx[k],ny=x.s+dy[k];
- if(grid[nx][ny]==1){
- if(dist[x.f][x.s]+1<dist[nx][ny]){
- dist[nx][ny]=dist[x.f][x.s]+1;
- from[nx][ny]=k;
- q.push({nx,ny});
- }
- }
- }
- }
- //backtracking to find optimal path
- string ret="";
- int tmpX=sx,tmpY=sy;
- while(tmpX!=fx || tmpY!=fy){
- int k=from[tmpX][tmpY];
- tmpX-=dx[k],tmpY-=dy[k];
- ret+=dir[k];
- }
- cout<<ret<<endl;
- }
Add Comment
Please, Sign In to add comment