fork download
copy 
  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 yesc cout << "YES\n"
  7. #define noc 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;
  23. char graph[1010][1010];
  24. bool vis[1010][1010][4];
  25.  
  26. bool check(int x, int y, int dir) {
  27. 	return x>=0 && y>=0 && x<n && y<m && !vis[x][y][dir] && 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, dir)) {
  45. 			gr.push({X, Y, dir, 0});
  46. 			vis[X][Y][dir]=true;
  47. 		}
  48. 	}
  49.  
  50. 	while(!gr.empty()) {
  51. 		node curr=gr.front();
  52. 		gr.pop();
  53.  
  54. 		if(graph[curr.x][curr.y]=='T') 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, nDir)) continue;
  63. 			//curr.turns+=(curr.dir != nDir);
  64. 			if(graph[X][Y]=='T') return true;
  65.  
  66. 			gr.push({X, Y, nDir, nTurns});
  67. 			vis[X][Y][nDir]=true;
  68. 		}
  69.  
  70. 	}
  71.  
  72. 	return false;
  73. }
  74.  
  75. void solve() {
  76. 	scanf("%d %d", &n, &m);
  77.  
  78. 	for(int i=0; i<n; i++) {
  79. 		for(int j=0; j<m; j++) {
  80. 			cin >> graph[i][j];
  81.  
  82. 			if(graph[i][j]=='S') {
  83. 				sx=i; sy=j;
  84. 			}
  85. 		}
  86. 	}
  87.  
  88. 	if(bfs()) yup;
  89. 	else nope;
  90. }
  91.  
  92. int main() {
  93. 	fast();
  94.  
  95. 	int t=1;
  96. 	//cin >> t;
  97. 	while(t--)
  98. 	solve();
  99.  
  100.  
  101. 	return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 5
..S..
****.
T....
****.
.....
stdout
copy 
NO
https://ideone.com/7UjK4p
language:
C++ (gcc 8.3)
created:
14 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!