fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  5. #define all(x) (x).begin(),(x).end()
  6. #define yes cout << "YES\n"
  7. #define no cout << "NO\n"
  8. #define yup printf("YES\n")
  9. #define nope printf("NO\n")
  10. #define PI 3.141592653589793238462643383279502884L
  11. typedef long long ll;
  12. const int MOD = 1000000007;
  13. const int N=1010;
  14.  
  15. struct node {
  16. 	int x, y, dir, turns;
  17. };
  18.  
  19. int dx[]={0, 0, 1, -1};
  20. int dy[]={1, -1, 0, 0};
  21.  
  22. int n, m, sx=-1, sy=-1, tx=-1, ty=-1;
  23. char graph[N][N];
  24. bool vis[N][N][4][3];
  25.  
  26. bool check(int x, int y) {
  27. 	return x>=0 && y>=0 && x<n && y<m && graph[x][y]!='*';
  28. }
  29.  
  30. int getDir(int dx, int dy) {
  31. 	if(dx==0 && dy==1) return 0; //left
  32. 	if(dx==0 && dy==-1) return 1; //right
  33. 	if(dx==1 && dy==0) return 2; //down
  34. 	return 3; //up
  35. }
  36.  
  37. bool bfs() {
  38. 	queue<node> gr;
  39.  
  40. 	for(int i=0; i<4; i++) {
  41. 		int X=sx+dx[i], Y=sy+dy[i];
  42. 		int dir=getDir(dx[i], dy[i]);
  43.  
  44. 		if(check(X, Y)) {
  45. 			gr.push({X, Y, dir, 0});
  46. 			vis[X][Y][dir][0]=true;
  47. 		}
  48. 	}
  49.  
  50. 	while(!gr.empty()) {
  51. 		node curr=gr.front();
  52. 		gr.pop();
  53.  
  54. 		if(curr.x==tx && curr.y==ty) return true;
  55.  
  56. 		for(int i=0; i<4; i++) {
  57. 			int X=curr.x+dx[i], Y=curr.y+dy[i];
  58. 			int nDir=getDir(dx[i], dy[i]), nTurns=curr.turns;
  59.  
  60. 			if(curr.dir != nDir) nTurns++;
  61. 			if(nTurns>2) continue;
  62. 			if(!check(X, Y)) continue;
  63. 			//curr.turns+=(curr.dir != nDir);
  64. 			if(graph[X][Y]=='T') return true;
  65.  
  66. 			if(!vis[X][Y][nDir][nTurns]) {
  67. 				gr.push({X, Y, nDir, nTurns});
  68. 			    vis[X][Y][nDir][nTurns]=true;
  69. 			}
  70. 		}
  71.  
  72. 	}
  73.  
  74. 	return false;
  75. }
  76.  
  77. void solve() {
  78. 	cin >> n >> m;
  79.  
  80. 	for(int i=0; i<n; i++) {
  81. 		for(int j=0; j<m; j++) {
  82. 			cin >> graph[i][j];
  83.  
  84. 			if(graph[i][j]=='S') {
  85. 				sx=i; sy=j;
  86. 			}
  87. 			if(graph[i][j]=='T') {
  88. 				tx=i; ty=j;
  89. 			}
  90.  
  91. 		}
  92. 	}
  93.  
  94. 	if(bfs()) yes;
  95. 	else no;
  96. }
  97.  
  98. int main() {
  99. 	fast();
  100.  
  101. 	int t=1;
  102. 	//cin >> t;
  103. 	while(t--)
  104. 	solve();
  105.  
  106.  
  107. 	return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
NO
https://ideone.com/vkoZZm
language:
C++ (gcc 8.3)
created:
11 hours 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!