fork(7) download
copy 
  1. #include <bits/stdc++.h>
  2. #define left lolkek
  3.  
  4. using namespace std;
  5.  
  6. int n, m;
  7. vector<int> dx = {-1, 1, 0, 0};
  8. vector<int> dy = {0, 0, -1, 1};
  9. vector<char> dir = {'L', 'R', 'U', 'D'};
  10. vector<vector<int>> grid;
  11. vector<vector<int>> left;
  12. vector<vector<int>> up;
  13. int si = 0;
  14. int sj = 0;
  15. int ti = 0;
  16. int tj = 0;
  17.  
  18. string path;
  19.  
  20. void dfs(int i, int j, int d, int t) {
  21.     path += dir[d];
  22.     if (t > 1 || i < 1 || i > n || j < 1 || j > m || grid[i][j] == 1) {
  23.         path.pop_back();
  24.         return;
  25.     }
  26.     if (j == tj) {
  27.         int occ = up[max(ti, i)][j] - up[min(ti, i) - 1][j];
  28.         if (occ == 0) {
  29.             cout << "YES";
  30.             exit(0);
  31.         }
  32.     } else if (i == ti) {
  33.         int occ = left[i][max(tj, j)] - left[i][min(tj, j) - 1];
  34.         if (occ == 0) {
  35.             cout << "YES";
  36.             exit(0);
  37.         }
  38.     }
  39.     for (int d1 = 0; d1 < 4; d1++) {
  40.         if (d1 == d || d1 == (d ^ 1)) continue;
  41.         dfs(i + dy[d1], j + dx[d1], d1, t + 1);
  42.     }
  43.     dfs(i + dy[d], j + dx[d], d, t);
  44.     path.pop_back();
  45. }
  46.  
  47. int main()
  48. {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(0);
  51.     cout.tie(0);
  52.     cin >> n >> m;
  53.     grid.assign(n + 1, vector<int>(m + 1, 0));
  54.     string inp;
  55.     for (int i = 0; i < n; i++) {
  56.         cin >> inp;
  57.         for (int j = 0; j < m; j++) {
  58.             if (inp[j] == '*') {
  59.                 grid[i + 1][j + 1] = 1;
  60.             }
  61.             if (inp[j] == 'S') {
  62.                 si = i + 1;
  63.                 sj = j + 1;
  64.             } else if (inp[j] == 'T') {
  65.                 ti = i + 1;
  66.                 tj = j + 1;
  67.             }
  68.         }
  69.     }
  70.     left.assign(n + 1, vector<int>(m + 1, 0));
  71.     up.assign(n + 1, vector<int>(m + 1, 0));
  72.     for (int i = 1; i <= n; i++) {
  73.         for (int j = 1; j <= m; j++) {
  74.             left[i][j] = left[i][j - 1] + grid[i][j];
  75.             up[i][j] = up[i - 1][j] + grid[i][j];
  76.         }
  77.     }
  78.     for (int d = 0; d < 4; d++) {
  79.         dfs(si + dy[d], sj + dx[d], d, 0);
  80.     }
  81.     cout << "NO";
  82. }
  83.  
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
3 3
S..
.*.
..T
stdout
copy 
YES
https://ideone.com/IoSts1
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!