제출 #1140539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140539		Faisal_Saqib	Toy (CEOI24_toy)	C++20	35 / 100	182 ms	12104 KiB

Main

#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=100;
char grid[N][N];
int pre_row[N][N],pre_col[N][N];
bitset<N> seen[N][N][N];
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.yh][cur.xv][cur.yv]);
	// {
	// 	return 1;
	// }	
	// return 0;
}
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.yh][cur.xv][cur.yv]=0;
}
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;;
						seen[i][j-L][i-U][j]=1;
					}
				}
			}
		}
	}
	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.yh<<' '<<it.xv<<' '<<it.yv<<endl;
		if(grid[it.xh][it.yv]=='*')
		{
			cout<<"YES"<<'\n';
			return 0;
		}
		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';
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27