Submission #1140565

#TimeUsernameProblemLanguageResultExecution timeMemory
1140565Faisal_SaqibToy (CEOI24_toy)C++20
0 / 100
1602 ms169844 KiB
#include <bits/stdc++.h>

using namespace std;

#define State pair<pair<int,int>,pair<int,int>>
#define xh first.first
#define yh first.second
#define xv second.first
#define yv second.second

const int N=300;
const int M=90; // try setting it to 181
char grid[N][N];
int pre_row[N][N],pre_col[N][N];
bitset<N> seen[N][M][M];
int k,l,h,w;
int get_row(int x,int y)
{
	return pre_row[x][y+k]-pre_row[x][y];
}
int get_col(int x,int y)
{
	return pre_col[x+l][y]-pre_col[x][y];
}
// set<State> valid;
bool Valid(State& cur)
{
	return (min({cur.xh,cur.yh,cur.xv,cur.yv})>=0 and max(cur.xh,cur.xv)<h and max(cur.yh,cur.yv)<w and seen[cur.xh][cur.yv-cur.yh][cur.xh-cur.xv][cur.yv]);
}
State make_state(int x,int y,int x1,int y1)
{
	State tp;
	tp.xh=x;
	tp.yh=y;
	tp.xv=x1;
	tp.yv=y1;
	return tp;
}
queue<State> q;
void mark(State cur)
{
	q.push(cur);
	seen[cur.xh][cur.yv-cur.yh][cur.xh-cur.xv][cur.yv]=0;
}
// let  change state to (x,y,U,L)
// U <= 
int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin>>w>>h>>k>>l;
	int xh1,yh1,xv1,yv1;
	cin>>xh1>>yh1>>xv1>>yv1;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>grid[i][j];
			pre_row[i][j+1]=pre_row[i][j]+(grid[i][j]=='X');
			pre_col[i+1][j]=pre_col[i][j]+(grid[i][j]=='X');
		}
	}
	for(int U=0;U<l;U++)
	{
		int D=l-1-U;
		if(D<0)break;
		for(int L=0;L<k;L++)
		{
			int R=k-1-L;
			if(R<0)break;
			for(int i=U;(i+D)<h;i++)
			{
				for(int j=L;(j+R)<w;j++)
				{
					if(get_row(i,j-L)==0 and get_col(i-U,j)==0)
					{
						// cout<<"Valid "<<i<<' '<<j-L<<' '<<i-U<<' '<<j<<endl;;
						// H * 
						// seen[i][j-L][i-U][j]=1;
						seen[i][L][U][j]=1;
						// change to [i][L][U][j]
					}
				}
			}
		}
	}
	vector<pair<int,int>> dir={{-1,0},{0,-1},{0,1},{1,0}};
	mark(make_state(yh1,xh1,yv1,xv1));
	while(q.size()>0)
	{
		auto it=q.front();
		q.pop();
		// cout<<"At "<<it.xh<<' '<<it.yv-it.yh<<' '<<it.xh-it.xv<<' '<<it.yv<<endl;
		if(grid[it.xh][it.yv]=='*')
		{
			cout<<"YES"<<'\n';
			return 0;
		}

		// it.yh=it.yv-it.yh;

		// it.xv=it.xh-it.xv;

		for(auto&[dx,dy]:dir)
		{
			it.xh+=dx;
			it.yh+=dy;
			if(Valid(it))
				mark(it);
			it.xh-=dx;
			it.yh-=dy;
		}
		for(auto&[dx,dy]:dir)
		{
			it.xv+=dx;
			it.yv+=dy;
			if(Valid(it))
				mark(it);
			it.xv-=dx;
			it.yv-=dy;
		}
	}
	cout<<"NO"<<'\n';
}
#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...