Advertisement
_no0B

Untitled

Nov 1st, 2021
941
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int dis[1005][1005];
  6.  
  7. string str[1005];
  8.  
  9. const string order = "DLRU";
  10.  
  11. int dxx[] = {1,0,0,-1};
  12. int dyy[] = {0,-1,1,0};
  13.  
  14. void bfs(int row , int col)
  15. {
  16.     memset(dis,-1,sizeof dis);
  17.     queue < pair < int , int > > que;
  18.     que.push({row,col});
  19.     dis[row][col] = 0;
  20.     while(!que.empty()){
  21.         row = que.front().first , col = que.front().second;
  22.         que.pop();
  23.         for(int i = 0 ; i < 4 ; i++){
  24.             int x = row + dxx[i] , y = col + dyy[i];
  25.             if(dis[x][y] == -1 && str[x][y] != '*'){
  26.                 dis[x][y] = dis[row][col] + 1;
  27.                 que.push({x,y});
  28.             }
  29.         }
  30.     }
  31.  
  32. }
  33.  
  34.  
  35.  
  36. string dfs(int row , int col , int rem)
  37. {
  38.     if(dis[row][col] > rem || dis[row][col] == -1) return "IMPOSSIBLE";
  39.     if(rem == 0) return "";
  40.     for(int i = 0 ; i < 4 ; i++){
  41.         int x = row + dxx[i] , y = col + dyy[i];
  42.         string ans = dfs(x , y , rem-1);
  43.         if(ans != "IMPOSSIBLE"){
  44.             return order[i] + ans;
  45.         }
  46.     }
  47.     return "IMPOSSIBLE";
  48. }
  49.  
  50. int main()
  51. {
  52.     /// problem B
  53.     int n , m , k;
  54.     cin>>n>>m>>k;
  55.     for(int i = 1 ; i <= n ; i++){
  56.         cin>>str[i];
  57.         str[i] = "*" + str[i] + "*";
  58.     }
  59.     for(int i = 0 ; i < m+2 ; i++) str[0] += "*";
  60.     str[n+1] = str[0];
  61. //    for(int i = 0 ; i <= n+1 ; i++) cout<<str[i]<<endl;
  62.     for(int i = 1 ; i <= n ; i++){
  63.         for(int j = 1 ; j <= m ; j++){
  64.             if(str[i][j] == 'X'){
  65.                 bfs(i,j);
  66. //                cout<<"okay\n";
  67.                 string ans = dfs(i , j , k);
  68.                 cout<<ans<<endl;
  69.                 return 0;
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement