This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
vector<vector<int>>najljevlji,najdesniji,najgornji,najdonji;
vector<vector<char>>grid;
int w,h,k,l,xh,yh,xv,yv,x,y;
vector<vector<bool>>visited;
void dfs(int x1,int y1){
if(visited[x1][y1])return;
visited[x1][y1]=true;
if(grid[x1+1][y1]!='X'){
if(!((najdesniji[x1][y1]>najljevlji[x1+1][y1])||(najdesniji[x1+1][y1]>najljevlji[x1][y1])))
if(najdesniji[x1+1][y1]<=najljevlji[x1+1][y1])dfs(x1+1,y1);
}
if(grid[x1-1][y1]!='X'){
if(!((najdesniji[x1][y1]>najljevlji[x1-1][y1])||(najdesniji[x1-1][y1]>najljevlji[x1][y1])))
if(najdesniji[x1-1][y1]<=najljevlji[x1-1][y])dfs(x1-1,y1);
}
if(grid[x1][y1+1]!='X'){
if(!((najgornji[x1][y1]<najdonji[x1][y1+1])||(najgornji[x1][y1+1]<najdonji[x1][y1])))
if(najgornji[x1][y1+1]>=najdonji[x1][y1+1])dfs(x1,y1+1);
}
if(grid[x1][y1-1]!='X'){
if(!((najgornji[x1][y1]<najdonji[x1][y1-1])||(najgornji[x1][y1-1]<najdonji[x1][y1])))
if(najgornji[x1][y1-1]>=najdonji[x1][y1-1])dfs(x1,y1-1);
}
}
signed main(){
cin>>w>>h>>k>>l>>xh>>yh>>xv>>yv;xh++;yh++;xv++;yv++;
grid.resize(h+2,vector<char>(w+2,'X'));
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin>>grid[i][j];
if(grid[i][j]=='*'){
x=i;y=j;
}
}
}
visited.resize(h+2,vector<bool>(w+2,false));
najljevlji.resize(h+2,vector<int>(w+2,k-1));
najdesniji.resize(h+2,vector<int>(w+2,0));
najdonji.resize(h+2,vector<int>(w+2,0));
najgornji.resize(h+2,vector<int>(w+2,l-1));
for(int i=0;i<h+2;i++){
for(int j=0;j<w+2;j++){
if(grid[i][j]=='X'){
for(int num=0;num<k;num++){
if((j+num+1)<w+2){
if(grid[i][j+num+1]!='X')najljevlji[i][j+num+1]=num;
else break;
}else break;
}
for(int num=0;num<l;num++){
if((i+num+1)<h+2){
if(grid[i+num+1][j]!='X')najgornji[i+num+1][j]=num;
else break;
}else break;
}
}
}
}
for(int i=h+1;i>=0;i--){
for(int j=w+1;j>=0;j--){
if(grid[i][j]=='X'){
for(int num=0;num<k;num++){
if((j-num-1)>=0){
if(grid[i][j-num-1]!='X')najdesniji[i][j-num-1]=k-1-num;
else break;
}else break;
}
for(int num=0;num<l;num++){
if((i-num-1)>=0){
if(grid[i-num-1][j]!='X')najdonji[i-num-1][j]=l-1-num;
else break;
}else break;
}
}
}
}
dfs(yh,xv);
cout<<((visited[x][y]==true)?"YES\n":"NO\n");
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |