fork download
  1. #include<bits/stdc++.h>
  2. #define sz(a) int((a).size())
  3. #define int long long
  4. #define pb push_back
  5. #define eb emplace_back
  6. #define mp make_pair
  7. #define mt make_tuple
  8. #define F first
  9. #define S second
  10. #define ld(a) while(a--)
  11. #define tci(v,i) for(auto i=v.begin();i!=v.end();i++)
  12. #define tcf(v,i) for(auto i : v)
  13. #define all(v) v.begin(),v.end()
  14. #define rep(i,start,lim) for(long long (i)=(start);i<(lim);i++)
  15. #define repd(i,start,lim) for(long long (i)=(start);i>=(lim);i--)
  16. #define present(c,x) (find(all(c),x) != (c).end())
  17. #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  18. #define osit ostream_iterator
  19. #define INF 0x3f3f3f3f
  20. #define LLINF 1000111000111000111LL
  21. #define PI 3.14159265358979323
  22. #define endl '\n'
  23. #ifdef WIN32
  24. #define getchar_unlocked getchar
  25. #endif
  26. #define gc getchar
  27. #define trace1(x) cerr<<#x<<": "<<x<<endl
  28. #define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  29. #define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  30. #define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  31. #define trace5(a, b, c, d, e) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  32. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  33. #define N 1000006
  34. using namespace std;
  35. typedef vector<int> vi;
  36. typedef vector<vi> vvi;
  37. typedef long long ll;
  38. typedef vector<long long> vll;
  39. typedef vector<vll> vvll;
  40. typedef long double ld;
  41. typedef pair<int,int> ii;
  42. typedef vector<ii> vii;
  43. typedef vector<vii> vvii;
  44. typedef tuple<int,int,int> iii;
  45. typedef set<int> si;
  46. typedef complex<double> pnt;
  47. typedef vector<pnt> vpnt;
  48. typedef priority_queue<ii,vii,greater<ii> > spq;
  49. const ll MOD=1000000007LL;
  50. template<typename T> T sqr(T x){return x*x;}
  51. template<typename T> T gcd(T a,T b){if(a==0) return b; return gcd(b%a,a);}
  52. template<typename T>void read(T &x) { register T c = gc(); x = 0; int t = 0; if (c == '-') t = 1, c = gc(); for (; (c < 48 || c>57); c = gc()); for (; c > 47 && c < 58; c = gc()) { x = (x << 1) + (x << 3) + c - 48; }if (t) x = -x; }
  53. template<typename T> T power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;} //using this instead of inbuilt pow due to precision issues in that
  54. template<typename T> ll roundp(T x){ll ans=x;if(x-floor(x)<=0.001) ans=floor(x);else if(ceil(x)-x<=0.001) ans=ceil(x);return ans;}
  55. char a[1005][1005];
  56. int vis[1005][1005];
  57. int n,m;
  58. bool f=0;
  59. void go(int x,int y,int ct,int px,int py){
  60. if(x<0 || y<0 || x>=n || y>=m || a[x][y]=='*' || ct>2 || vis[x][y]) return ;
  61. //trace3(x,y,ct);
  62. vis[x][y]=1;
  63. if(a[x][y]=='S'){
  64. trace1(ct);
  65. f=1; return;
  66. }
  67. go(x+1,y,ct+(px!=x+1 && py!=y),x,y);
  68. go(x-1,y,ct+(px!=x-1 && py!=y),x,y);
  69. go(x,y+1,ct+(px!=x && py!=y+1),x,y);
  70. go(x,y-1,ct+(px!=x && py!=y-1),x,y);
  71. }
  72. int32_t main(){
  73. sync;
  74. cin>>n>>m;
  75. int x=0,y=0;
  76. rep(i,0,n){
  77. rep(j,0,m){
  78. cin>>a[i][j];
  79. if(a[i][j]=='T'){
  80. x=i,y=j;
  81. }
  82. }
  83. }
  84. go(x,y,0,x,y);
  85. if(f) cout<<"YES";
  86. else cout<<"NO";
  87.  
  88. }
  89.  
  90.  
Success #stdin #stdout 0s 24928KB
stdin
Standard input is empty
stdout
NO