fork(6) download
  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
stdin
3 3
S..
.*.
..T
stdout
YES