ec1117

Untitled

Jan 23rd, 2022 (edited)
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.14 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5.  
  6.  
  7. #define FOR(i,a,b) for(int i=a;i<b;i++)
  8. #define For(i,b) FOR(i,0,b)
  9. #define pi pair<int,int>
  10. #define f first
  11. #define s second
  12.  
  13.  
  14. const int MX=105;
  15. int grid[MX][MX];
  16. int dist[MX][MX];
  17. int from[MX][MX];
  18. int dx[4]={1,-1,0,0};
  19. int dy[4]={0,0,1,-1};
  20. char dir[4]={'U','D','L','R'};//opposite of dx,dy
  21.  
  22. int main(){
  23. int n,m;cin>>n>>m;
  24. int sx,sy,fx,fy;
  25. For(i,n){
  26. string S;cin>>S;
  27. For(j,m){
  28. if(S[j]=='#')grid[i][j]=0;
  29. else grid[i][j]=1;
  30. if(S[j]=='S')sx=i,sy=j;
  31. if(S[j]=='F')fx=i,fy=j;
  32. }
  33. }
  34. For(i,n)For(j,m)dist[i][j]=1e9;
  35.  
  36. //BFS from end point
  37. queue<pi> q;
  38. q.push({fx,fy});
  39. dist[fx][fy]=0;
  40. while((int)q.size()){
  41. pi x=q.front();q.pop();
  42. For(k,4){
  43. int nx=x.f+dx[k],ny=x.s+dy[k];
  44. if(grid[nx][ny]==1){
  45. if(dist[x.f][x.s]+1<dist[nx][ny]){
  46. dist[nx][ny]=dist[x.f][x.s]+1;
  47. from[nx][ny]=k;
  48. q.push({nx,ny});
  49. }
  50. }
  51. }
  52. }
  53.  
  54. //backtracking to find optimal path
  55. string ret="";
  56. int tmpX=sx,tmpY=sy;
  57. while(tmpX!=fx || tmpY!=fy){
  58. int k=from[tmpX][tmpY];
  59. tmpX-=dx[k],tmpY-=dy[k];
  60. ret+=dir[k];
  61. }
  62. cout<<ret<<endl;
  63. }
  64.  
Add Comment
Please, Sign In to add comment