Submission #1140711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140711		MuhammadSaram	Toy (CEOI24_toy)	C++20	0 / 100	0 ms	580 KiB

Main

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

const int M = 1500,h3=1e6+3;

struct has
{
	long long operator() (tuple<short,short,short,short> p) const
	{
		return get<0>(p)*h3+get<1>(p)*727+get<2>(p)*31+get<3>(p);
	}
};

int pre[M+1][M+1],n,m,h,v,tx,ty;
cc_hash_table<tuple<short,short,short,short>,bool,has> se;

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(short xh,short yh,short xv,short yv)
{
	se[{xh,yh,xv,yv}]=1;
	if (xh==tx && yv==ty)
	{
		cout<<"YES"<<endl;
		exit(0);
	}
	if (yh<yv && clr(xh,yh+1,xh,yh+h))
	{
		if (se.find({xh,yh+1,xv,yv})==se.end()) dfs(xh,yh+1,xv,yv);	
	}
	if (yv<yh+h-1 && clr(xh,yh-1,xh,yh+h-2))
	{
		if (se.find({xh,yh-1,xv,yv})==se.end()) dfs(xh,yh-1,xv,yv);
	}
	if (xh<xv+v-1 && clr(xh+1,yh,xh+1,yh+h-1))
	{
		if (se.find({xh+1,yh,xv,yv})==se.end()) dfs(xh+1,yh,xv,yv);
	}
	if (xh>xv && clr(xh-1,yh,xh-1,yh+h-1))
	{
		if (se.find({xh-1,yh,xv,yv})==se.end()) dfs(xh-1,yh,xv,yv);
	}
	if (yv<yh+h-1 && clr(xv,yv+1,xv+v-1,yv+1))
	{
		if (se.find({xh,yh,xv,yv+1})==se.end()) dfs(xh,yh,xv,yv+1);
	}
	if (yv>yh && clr(xv,yv-1,xv+v-1,yv-1))
	{
		if (se.find({xh,yh,xv,yv-1})==se.end()) dfs(xh,yh,xv,yv-1);
	}
	if (xv<xh && clr(xv+1,yv,xv+v,yv))
	{
		if (se.find({xh,yh,xv+1,yv})==se.end()) dfs(xh,yh,xv+1,yv);
	}
	if (xv+v-1>xh && clr(xv-1,yv,xv+v-2,yv))
	{
		if (se.find({xh,yh,xv-1,yv})==se.end()) dfs(xh,yh,xv-1,yv);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	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');
			if (a[i][j]=='*')
				tx=i,ty=j;
		}
	dfs(xh,yh,xv,yv);
	cout<<"NO"<<endl;
		
	return 0;
}

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