Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int dis[1005][1005];
- string str[1005];
- const string order = "DLRU";
- int dxx[] = {1,0,0,-1};
- int dyy[] = {0,-1,1,0};
- void bfs(int row , int col)
- {
- memset(dis,-1,sizeof dis);
- queue < pair < int , int > > que;
- que.push({row,col});
- dis[row][col] = 0;
- while(!que.empty()){
- row = que.front().first , col = que.front().second;
- que.pop();
- for(int i = 0 ; i < 4 ; i++){
- int x = row + dxx[i] , y = col + dyy[i];
- if(dis[x][y] == -1 && str[x][y] != '*'){
- dis[x][y] = dis[row][col] + 1;
- que.push({x,y});
- }
- }
- }
- }
- string dfs(int row , int col , int rem)
- {
- if(dis[row][col] > rem || dis[row][col] == -1) return "IMPOSSIBLE";
- if(rem == 0) return "";
- for(int i = 0 ; i < 4 ; i++){
- int x = row + dxx[i] , y = col + dyy[i];
- string ans = dfs(x , y , rem-1);
- if(ans != "IMPOSSIBLE"){
- return order[i] + ans;
- }
- }
- return "IMPOSSIBLE";
- }
- int main()
- {
- /// problem B
- int n , m , k;
- cin>>n>>m>>k;
- for(int i = 1 ; i <= n ; i++){
- cin>>str[i];
- str[i] = "*" + str[i] + "*";
- }
- for(int i = 0 ; i < m+2 ; i++) str[0] += "*";
- str[n+1] = str[0];
- // for(int i = 0 ; i <= n+1 ; i++) cout<<str[i]<<endl;
- for(int i = 1 ; i <= n ; i++){
- for(int j = 1 ; j <= m ; j++){
- if(str[i][j] == 'X'){
- bfs(i,j);
- // cout<<"okay\n";
- string ans = dfs(i , j , k);
- cout<<ans<<endl;
- return 0;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement