fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. boundaries:
  6. - row 1 or n
  7. - col 1 or m
  8. */
  9.  
  10. #define ll long long
  11. #define INF 1000000000
  12. #define MAX 1005 
  13.  
  14. char di[4] = {'U', 'D', 'L', 'R'};
  15. int dx[4] = {-1, 1, 0, 0};
  16. int dy[4] = {0, 0, -1, 1};
  17.  
  18. char a[MAX][MAX];
  19. int n, m;
  20.  
  21. pair<int, int> par[MAX][MAX];
  22. char SongNghi[MAX][MAX];
  23. int dist_m[MAX][MAX];
  24. int dist_p[MAX][MAX]; 
  25.  
  26. void solve() {
  27.     cin >> n >> m; 
  28.  
  29.     int stx = -1, sty = -1;
  30.     for (int i = 1; i <= n; i++) {
  31.         for (int j = 1; j <= m; j++) {
  32.             cin >> a[i][j]; 
  33.             if (a[i][j] == 'A') {
  34.                 stx = i;
  35.                 sty = j;
  36.             }
  37.         }
  38.     }
  39.  
  40.     for (int i = 0; i <= n; i++) {
  41.         for (int j = 0; j <= m; j++) {
  42.             dist_m[i][j] = dist_p[i][j] = INF;
  43.             par[i][j] = {i, j};
  44.         }
  45.     }
  46.  
  47.     queue<pair<int, int>> q;
  48.     for (int i = 1; i <= n; i++) {
  49.         for (int j = 1; j <= m; j++) {
  50.             if (a[i][j] == 'M') {
  51.                 q.push({i, j});
  52.                 dist_m[i][j] = 0;
  53.             }
  54.         }
  55.     }
  56.  
  57.     while (!q.empty()) {
  58.         pair<int, int> u = q.front();
  59.         q.pop();
  60.  
  61.         int x = u.first;
  62.         int y = u.second;
  63.  
  64.         for (int i = 0; i < 4; i++) {
  65.             int nx = x + dx[i]; 
  66.             int ny = y + dy[i];
  67.  
  68.             if (nx < 0 || nx > n || ny < 0 || ny > m || a[nx][ny] == '#' || dist_p[nx][ny] <= dist_p[x][y] + 1) continue;
  69.             dist_p[nx][ny] = dist_p[x][y] + 1; 
  70.             q.push({nx, ny});
  71.         }
  72.     }
  73.  
  74.     q.push({stx, sty});
  75.     while (!q.empty()) {
  76.         pair<int, int> u = q.front(); 
  77.         q.pop();
  78.  
  79.         int x = u.first; 
  80.         int y = u.second;
  81.  
  82.         for (int i = 0; i < 4; i++) {
  83.             int nx = x + dx[i]; 
  84.             int ny = y + dy[i];
  85.  
  86.             if (nx < 0 || nx > n || ny < 0 || ny > m || a[nx][ny] == '#' || dist_p[nx][ny] <= dist_p[x][y] + 1) continue;
  87.             if (dist_p[nx][ny] >= dist_m[nx][ny]) continue;
  88.  
  89.             dist_p[nx][ny] = dist_p[x][y] + 1;
  90.             SongNghi[nx][ny] = di[i];
  91.             par[nx][ny] = {x, y};
  92.             q.push({nx, ny});
  93.         }
  94.     }
  95.  
  96.     int enx = -1, eny = -1;
  97.     for (int i = 1; i <= n; i++) {
  98.         for (int j = 1; j <= m; j++) {
  99.             if (a[i][j] == '.' && (i == 1 || i == n) && dist_p[i][j] != INF) {
  100.                 enx = i; 
  101.                 eny = j;
  102.             } 
  103.  
  104.             if (a[i][j] == '.' && (j == 1 || j == m) && dist_p[i][j] != INF) {
  105.                 enx = i; 
  106.                 eny = j;
  107.             }
  108.         } 
  109.     }
  110.  
  111.     if (enx == -1 && eny == -1) {
  112.     	cout << "NO\n"; 
  113.         return;
  114.     }
  115.  
  116.     vector<char> answer; 
  117.     pair<int, int> cur = {enx, eny};
  118.  
  119.     while (cur.first != stx && cur.second != sty) {
  120.         answer.push_back(SongNghi[cur.first][cur.second]);
  121.         cur = par[cur.first][cur.second];
  122.     }
  123.  
  124.     reverse(answer.begin(), answer.end());
  125.     for (char c : answer) cout << c << '\n';
  126. }   
  127.  
  128. int main() {
  129.     solve();
  130. }
Success #stdin #stdout 0.01s 9752KB
comments (?)
stdin
copy 
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
stdout
copy 
NO
https://ideone.com/3pJtC8
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!