Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pi;
- #define f first
- #define s second
- #define pb push_back
- #define mp make_pair
- #define loop(n) for(int i=0; i<n; i++)
- #define rep(i, a, n) for(int i=a; i<n; i++)
- #define file_read freopen("input.txt", "r", stdin); \
- freopen("output.txt", "w", stdout);
- #define tc int t; cin>>t; while(t--)
- #define endl "\n"
- #define usainbolt cin.tie(0) -> sync_with_stdio(0)
- int mat[1000][1000];
- int n, m;
- int (*vis)[1000];
- int (*vis2)[1000];
- /*
- 0 - up
- 1 - right
- 2 - down
- 3 - left
- */
- bool inbounds(int x, int y){
- if(x<m && x>=0 && y<n && y>=0 && mat[y][x]!='*')
- return true;
- else
- return false;
- }
- void hasreached(int x, int y){
- if(mat[y][x]=='T'){
- cout<<"YES";
- exit(0);
- }
- }
- void mark_tiles(){
- for(int i=0; i<n; i++){
- for(int j=0; j<m; j++){
- if(vis[i][j]==0)
- continue;
- int x = j, y = i;
- bool b1, b2;
- b1 = b2 = true;
- switch(vis[y][x]){
- //turn horizontal
- case 1:
- for(int l=x-1, r=x+1; b1 || b2 == true; r++, l--){
- if(inbounds(l, y) && b1 && vis[y][l]!=2){
- hasreached(l, y);
- vis2[y][l] = 2;
- }
- else b1 = false;
- if(inbounds(r, y) && b2 && vis[y][r]!=2){
- hasreached(r, y);
- vis2[y][r] = 2;
- }
- else b2 = false;
- }
- break;
- //turn vertical
- case 2:
- for(int u=y-1, d=y+1; b1 || b2 == true; d++, u--){
- if(inbounds(x, u) && b1 && vis[u][x]!=1){
- hasreached(x, u);
- vis2[u][x] = 1;
- }
- else b1 = false;
- if(inbounds(x, d) && b2 && vis[d][x]!=1){
- hasreached(x, d);
- vis2[d][x] = 1;
- }
- else b2 = false;
- }
- break;
- }
- vis[i][j] = 0;
- }
- }
- int (*temp)[1000] = vis;
- vis = vis2;
- vis2 = temp;
- }
- // ..S..****.T....****......
- int main(void){
- usainbolt;
- //file_read
- cin>>n>>m;
- vis = (int(*)[1000])calloc(1000, 1000*4);
- vis2 = (int(*)[1000])calloc(1000, 4*1000);
- int h_x, h_y, b_x, b_y;
- for(int i=0; i<n; i++){
- for(int j=0; j<m; j++){
- char inp;
- cin>>inp;
- mat[i][j] = inp;
- if(mat[i][j]=='S')
- {
- h_x = j;
- h_y = i;
- vis[i][j] = 1;
- }
- }
- }
- bool b1, b2, b3, b4;
- b1 = b2 = b3 = b4 = true;
- for(int u=h_y-1, d=h_y+1, l=h_x-1, r=h_x+1; b1 || b2 || b3 || b4 == true; r++, l--, u--, d++){
- if(inbounds(h_x, u) && b1){
- hasreached(h_x, u);
- vis[u][h_x] = 1;
- }
- else b1 = false;
- if(inbounds(h_x, d) && b2){
- hasreached(h_x, d);
- vis[d][h_x] = 1;
- }
- else b2 = false;
- if(inbounds(l, h_y) && b3){
- hasreached(l, h_y);
- vis[h_y][l] = 2;
- }
- else b3 = false;
- if(inbounds(r, h_y) && b4){
- hasreached(r, h_y);
- vis[h_y][r] = 2;
- }
- else b4=false;
- }
- for(int i=0; i<2; i++){
- /*
- cout<<endl<<endl;
- for(int i=0; i<n; i++){
- for(int j=0; j<m; j++){
- cout<<vis[i][j];
- }
- cout<<endl;
- }
- */
- mark_tiles();
- }
- cout << "NO";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement