?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
82702495 |
Practice: AbhishekAg |
793B - 53 | C++17 (GCC 7-32) | Wrong answer on test 11 | 93 ms | 1816 KB | 2020-06-06 15:11:37 | 2020-06-06 15:11:37 |
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define mk make_pair #define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower); #define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper); using namespace std; typedef pair<int,int> pii; typedef pair<ll,ll>pll; typedef vector<ll> vl; typedef vector<pll> vpll; typedef vector<int> vi; typedef vector<pii> vpii; bool dfs(int i,int j,char dir,int turns,vector<vector<bool>>&vis,vector<vector<char>>&mat){ int n=mat.size(),m=mat[0].size(); if(i<0||i>=n||j<0||j>=m||turns>2) return false; if(vis[i][j]||mat[i][j]=='*') return false; if(mat[i][j]=='T') return true; vis[i][j]=true; int u=1,d=1,l=1,r=1; if(dir=='u') u--; if(dir=='d') d--; if(dir=='l') l--; if(dir=='r') r--; bool ans=false; ans|=dfs(i,j-1,'u',turns+u,vis,mat); ans|=dfs(i,j+1,'d',turns+d,vis,mat); ans|=dfs(i-1,j,'l',turns+l,vis,mat); ans|=dfs(i+1,j,'r',turns+r,vis,mat); return ans; } ll N=2e5+5; // ll N=101; ll MOD=1e9+7; int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // cout<<fixed<<setprecision(10); ll tests; tests=1; // cin>>tests; // vector<int>fre(N,0); while(tests--){ int n,m; cin>>n>>m; vector<vector<char>>mat(n,vector<char>(m)); int si,sj; for(int i=0;i<n;i++){ string s; cin>>s; for(int j=0;j<m;j++){ mat[i][j]=s[j]; if(s[j]=='S'){ si=i;sj=j; } } } vector<vector<bool>>vis(n,vector<bool>(m,false)); bool ans=false; ans|=dfs(si,sj,'u',0,vis,mat); for(int i=0;i<n;i++) for(int j=0;j<m;j++) vis[i][j]=false; ans|=dfs(si,sj,'d',0,vis,mat); for(int i=0;i<n;i++) for(int j=0;j<m;j++) vis[i][j]=false; ans|=dfs(si,sj,'l',0,vis,mat); for(int i=0;i<n;i++) for(int j=0;j<m;j++) vis[i][j]=false; ans|=dfs(si,sj,'r',0,vis,mat); if(ans) cout<<"YES"; else cout<<"NO"; } return 0; }
?
?
?
?