#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 1505
#define fi first
#define se second
#define pb push_back
typedef long double lo;
int h,w,k,l;
char dizi[lim][lim];
int arr[lim][lim];
int le[lim][lim],ri[lim][lim],up[lim][lim],down[lim][lim];
int vis[lim][lim];
inline bool check(int x,int y){
return x<=w && y<=h && x>=1 && y>=1;
}
int32_t main(){
faster
cin>>h>>w>>k>>l;
int p1,p2,pp1,pp2;cin>>p1>>p2>>pp1>>pp2;
int tar1,tar2;
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
cin>>dizi[i][j];
if(dizi[i][j]=='X')arr[i][j]=-1;
else if(dizi[i][j]=='*'){tar1=i,tar2=j;}
}
}
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
le[i][j]=le[i][j-1]+1;
if(arr[i][j]==-1)le[i][j]=0;
}
for(int j=h;j>=1;j--){
ri[i][j]=ri[i][j+1]+1;
if(arr[i][j]==-1)ri[i][j]=0;
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
up[j][i]=up[j-1][i]+1;
if(arr[j][i]==-1)up[j][i]=0;
}
for(int j=w;j>=1;j--){
down[j][i]=down[j+1][i]+1;
if(arr[j][i]==-1)down[j][i]=0;
}
}
//~ for(int i=1;i<=w;i++){
//~ for(int j=1;j<=h;j++){
//~ cout<<down[i][j]<<" ";
//~ }
//~ cout<<endl;
//~ }
p2++;
pp1++;
queue<pair<int,int>> qu;
qu.push({p2,pp1});
while(qu.size()){
int x=qu.front().fi,y=qu.front().se;
//cout<<x<<" "<<y<<endl;
qu.pop();
if(vis[x][y])continue;
vis[x][y]=1;
if(check(x+1,y) && arr[x+1][y]!=-1 && min(le[x][y]+ri[x][y]-1,le[x+1][y]+ri[x+1][y]-1)>=k)qu.push({x+1,y});
//cout<<min(le[x][y]+ri[x][y]-1,le[x+1][y]+ri[x+1][y]-1)<<" "<<check(x+1,y)<<" "<<arr[x+1][y]<<endl;
if(check(x-1,y) && arr[x-1][y]!=-1 && min(le[x][y]+ri[x][y]-1,le[x-1][y]+ri[x-1][y]-1)>=k)qu.push({x-1,y});
if(check(x,y+1) && arr[x][y+1]!=-1 && min(up[x][y]+down[x][y]-1,up[x][y+1]+down[x][y+1]-1)>=l)qu.push({x,y+1});
//cout<<up[x][y]<<" "<<down[x][y]<<" "<<up[x][y+1]<<" "<<down[x][y+1]<<" "<<check(x,y+1)<<" "<<arr[x][y+1]<<endl;
if(check(x,y-1) && arr[x][y-1]!=-1 && min(up[x][y]+down[x][y]-1,up[x][y-1]+down[x][y-1]-1)>=l)qu.push({x,y-1});
}
if(vis[tar1][tar2])cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
return 0;
}
| # | 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... |