SHARE
TWEET

Untitled

a guest Dec 8th, 2016 40 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int sz = 1010;
  5. const pair<int, int> no_parent = make_pair(-1, -1);
  6. int r, c;
  7. pair<int, int> src, dest, parent[sz][sz];
  8. char mat[sz][sz];
  9. queue<pair<int, int> > Q;
  10.  
  11. void bfs(){
  12.     Q.push(src);
  13.     parent[src.first][src.second] = no_parent;
  14.  
  15.     pair<int, int> left, right, up, down, u;
  16.  
  17.     while(!Q.empty()){
  18.         u = Q.front();
  19.         Q.pop();
  20.  
  21.         left = make_pair((u.first + c - 1)%c, u.second);
  22.         if(mat[left.first][left.second] != '#' && parent[left.first][left.second] == no_parent){
  23.             parent[left.first][left.second] = u;
  24.             Q.push(left);
  25.         }
  26.  
  27.         right = make_pair((u.first + 1)%c, u.second);
  28.         if(mat[right.first][right.second] != '#' && parent[right.first][right.second] == no_parent){
  29.             parent[right.first][right.second] = u;
  30.             Q.push(right);
  31.         }
  32.  
  33.         up = make_pair(u.first, (u.second + r - 1)%r);
  34.         if(mat[up.first][up.second] != '#' && parent[up.first][up.second] == no_parent){
  35.             parent[up.first][up.second] = u;
  36.             Q.push(up);
  37.         }
  38.  
  39.         down = make_pair(u.first, (u.second + 1)%r);
  40.         if(mat[down.first][down.second] != '#' && parent[down.first][down.second] == no_parent){
  41.             parent[down.first][down.second] = u;
  42.             Q.push(down);
  43.         }
  44.     }
  45. }
  46.  
  47. int main(){
  48.     ios_base::sync_with_stdio(false);
  49.     //freopen("input.in", "r", stdin);
  50.     cin >> r >> c;
  51.  
  52.     for(int j=0; j<r; j++){
  53.         for(int i=0; i<c; i++){
  54.             cin >> mat[i][j];
  55.             if(mat[i][j] == 'D')    dest = make_pair(i, j);
  56.             if(mat[i][j] == 'M')    src = make_pair(i, j);
  57.             parent[i][j] = no_parent;
  58.         }
  59.     }
  60.  
  61.     bfs();
  62.  
  63.     if(parent[dest.first][dest.second] == no_parent){
  64.         cout << "NO" << endl;
  65.     }else{
  66.         cout << "YES\n";
  67.  
  68.         //mark path with 'X's
  69.         pair<int, int> vert = parent[dest.first][dest.second];
  70.         while(vert != src){
  71.             mat[vert.first][vert.second] = 'X';
  72.             vert = parent[vert.first][vert.second];
  73.         }
  74.  
  75.         for(int j=0; j<r; j++){
  76.             for(int i=0; i<c; i++){
  77.                 cout << mat[i][j];
  78.             }
  79.             cout << "\n";
  80.         }
  81.     }
  82.  
  83.     return 0;
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top