Submission #1140649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140649		MuhammadSaram	Toy (CEOI24_toy)	C++20	14 / 100	1619 ms	446988 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int M = 1500;

int pre[M+1][M+1],n,m,h,v;
set<pair<int,int>> se;
unordered_set<int> it;

bool clr(int x,int y,int x1,int y1)
{
	if (x>=0 && y>=0 && x1<n && y1<m)
		return pre[x1+1][y1+1]-pre[x][y1+1]-pre[x1+1][y]+pre[x][y]==0;
	return 0;
}

void dfs(int vr,int hr)
{
	se.insert({vr,hr});
	int xh=hr/M,yh=hr%M,xv=vr/M,yv=vr%M;
	it.insert(xh*M+yv);
	if (yh<yv && clr(xh,yh+1,xh,yh+h))
	{
		if (se.find({vr,hr+1})==se.end()) dfs(vr,hr+1);	
	}
	if (yv<yh+h-1 && clr(xh,yh-1,xh,yh+h-2))
	{
		if (se.find({vr,hr-1})==se.end()) dfs(vr,hr-1);
	}
	if (xh<xv+v-1 && clr(xh+1,yh,xh+1,yh+h-1))
	{
		if (se.find({vr,hr+M})==se.end()) dfs(vr,hr+M);
	}
	if (xh>xv && clr(xh-1,yh,xh-1,yh+h-1))
	{
		if (se.find({vr,hr-M})==se.end()) dfs(vr,hr-M);
	}
	if (yv<yh+h-1 && clr(xv,yv+1,xv+v-1,yv+1))
	{
		if (se.find({vr+1,hr})==se.end()) dfs(vr+1,hr);
	}
	if (yv>yh && clr(xv,yv-1,xv+v-1,yv-1))
	{
		if (se.find({vr-1,hr})==se.end()) dfs(vr-1,hr);
	}
	if (xv<xh && clr(xv+1,yv,xv+v,yv))
	{
		if (se.find({vr+M,hr})==se.end()) dfs(vr+M,hr);
	}
	if (xv+v-1>xh && clr(xv-1,yv,xv+v-2,yv))
	{
		if (se.find({vr-M,hr})==se.end()) dfs(vr-M,hr);
	}
}

int main()
{
	cin>>m>>n>>h>>v;
	int xh,yh,xv,yv;
	cin>>xh>>yh>>xv>>yv;
	string a[n];
	for (int i=0;i<n;i++)
		cin>>a[i];
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			pre[i+1][j+1]=pre[i+1][j]+pre[i][j+1]-pre[i][j]+(a[i][j]=='X');
	dfs(yv*M+xv,yh*M+xh);
	string ans="NO";
	for (auto hs:it)
	{
		int i=hs/M,j=hs%M;
		if (a[i][j]=='*')
			ans="YES";
	}
	cout<<ans<<endl;
		
	return 0;
}

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