Submission #1300078

#TimeUsernameProblemLanguageResultExecution timeMemory
1300078elotelo966Toy (CEOI24_toy)C++20
0 / 100
12 ms12004 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...