fork(1) download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstring>
  3. #include <map>
  4. #include <deque>
  5. #include <queue>
  6. #include <stack>
  7. #include <sstream>
  8. #include <numeric>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <hash_map>
  14. #include <fstream>
  15. #include <string>
  16. #include <cstdlib>
  17. #include <ctime>
  18. #include <functional>
  19. #include <algorithm>
  20. #include <vector>
  21. #include <set>
  22. #include <complex>
  23. #include <list>
  24. #include <climits>
  25. #include <cctype>
  26. #include <bitset>
  27. using namespace std;
  28.  
  29. #define PI 3.14159265359
  30. #define all(v) v.begin(),v.end()
  31. #define sortva(v) sort(all(v))
  32. #define sortvd(v) sort(v.rbegin(),v.rend())
  33. #define sortaa(a,n) sort(a,a+n)
  34. #define sortad(a,n) sort(a,a+n),reverse(a,a+n)
  35. #define sfi1(v) scanf("%d",&v)
  36. #define sfi2(v1,v2) scanf("%d %d",&v1,&v2)
  37. #define sfi3(v1,v2,v3) scanf("%d %d %d",&v1,&v2,&v3)
  38. #define sfll1(v) scanf("%I64d",&v);
  39. #define sfll2(v1,v2) scanf("%I64d %I64d",&v1,&v2)
  40. #define sfll3(v1,v2,v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
  41. #define sfstr(v) scanf("%s", v);
  42. #define sz(v) v.size()
  43. #define ndl puts("")
  44. #define SS stringstream
  45. typedef long long ll;
  46. typedef unsigned long long ull;
  47. int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
  48. int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
  49.  
  50. ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
  51. ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
  52.  
  53. void PLAY() {
  54. #ifndef ONLINE_JUDGE
  55. 	freopen("input.txt", "r", stdin);
  56. 	freopen("output.txt", "w", stdout);
  57. #endif
  58. 	cout << fixed << setprecision(10);
  59. 	ios::sync_with_stdio(0);
  60. 	cin.tie(0);
  61. 	cout.tie(0);
  62. }
  63.  
  64. int n, m;
  65. char a[1005][1005];
  66. bool vis[1005][1005];
  67.  
  68.  
  69. bool valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < m; }
  70. int main() {
  71. 	PLAY();
  72.  
  73. 	cin >> n >> m;
  74. 	pair<int, int> start, end;
  75. 	for (int i = 0; i < n; i++) {
  76. 		for (int j = 0; j < m; j++) {
  77. 			cin >> a[i][j];
  78. 			if (a[i][j] == 'S') start = { i, j };
  79. 			else if (a[i][j] == 'T') end = { i, j };
  80. 		}
  81. 	}
  82.  
  83. 	queue<pair<pair<int, int>, pair<int,int>>> qu;
  84. 	qu.push({ start, { -1, 0 } });
  85. 	while (sz(qu)) {
  86. 		int x = qu.front().first.first;
  87. 		int y = qu.front().first.second;
  88. 		int lastmove = qu.front().second.first;
  89. 		int cnt = qu.front().second.second;
  90. 		qu.pop();
  91. 		if (make_pair(x, y) == end) {
  92. 			cout << "YES" << endl;
  93. 			return 0;
  94. 		}
  95. 		if (vis[x][y]) continue;
  96. 		vis[x][y] = true;
  97. 		for (int i = 0; i < 4; i++) {
  98. 			int tox = dx[i] + x;
  99. 			int toy = dy[i] + y;
  100. 			if (!valid(tox, toy)) continue;
  101. 			if (a[tox][toy] == '*') continue;
  102. 			if (lastmove == -1) {
  103. 				if (!vis[tox][toy])
  104. 					qu.push({ { tox, toy }, { i, 0 } });
  105. 			}
  106. 			else {
  107. 				int newcnt = cnt + bool(lastmove != i);
  108. 				if (newcnt > 2) continue;
  109. 				if (!vis[tox][toy])
  110. 					qu.push({ { tox, toy }, { i, newcnt } });
  111. 			}
  112. 		}
  113. 	}
  114. 	cout << "NO" << endl;
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 17200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/EmkO4J
language:
C++14 (gcc 8.3)
created:
7 years 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!