|

General

# Author Problem Lang Verdict Time Memory Sent Judged
82702495 Practice:
AbhishekAg
793B - 53 GNU C++17 Wrong answer on test 11 93 ms 1816 KB 2020-06-06 15:11:37 2020-06-06 15:11:37

→ Source
#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;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?