CF1898C Colorful Grid - CF题解 | 123hh2 = Keep moving forward

# CF1898C Colorful Grid

题目链接

# 题目大意

给定一个有 $n$ 条水平线和 $m$ 条垂直线组成的网格，水平线从上到下用 $1-n$ 编号，垂直线从左到右用 $1-m$ 编号， $(x,y)$ 表示第 $x$ 个水平线和第 $y$ 个垂直线的交点，当且仅当 $|x_1-x_2| + |y_1-y_2| = 1$ 时，两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 相邻

你可以将这个网格上的每条线段染上红色或蓝色，使得存在一个移动次数为 $k$ 的方案使得

起始点为 $(1,1)$ ，终点为 $(n,m)$
这个移动方案经过的第 $i$ 条线段的颜色与第 $i-1$ 和 $i+1$ 条线段的颜色不相同

若无法构造出这样的网格，输出 $NO$

否则输出 $YES$ 并先输出水平线段的着色方案，在输出垂直线段的着色方案

# 思路

首先我们可以发现最小移动次数必为 $minn = n+m-2$ ，，当给出的次数 $k$ 与 $minn$ 的差为奇数是是不存在移动方案的，即当 $k < minn 或 (k-minn)\%2 = 1$ 时，输出 $NO$

考虑可以存在路径的情况，此时 $(k-minn)\%2$ 取值为 $0$ 或 $2$ ，可以发现按最小移动方案移动到终点时，可以再走一个 $1*1$ 大小的正方形网格，并使移动次数 $+4$ ，即当 $(k-minn)\%2$ 取值为零时，可以先按最小移动次数的方案移动到终点并持续绕环直至次数等于 $k$ ，在考虑 $(k-minn)\%2$ 取值为 $2$ 时，可以在起点拐一个小弯，即直接向右走变成先向下，再向右，再向上走，这样可以使得总体移动步数多 $2$

接下来按照上述方案染色即可

# 代码

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=25;
	char C1[maxn][maxn],C2[maxn][maxn];
	signed main()
	{
	int t=read();
	while(t-->0)
	{
	int n=read(),m=read(),k=read();
	int minn=n+m-2,cnt=0;
	if((k<minn)\|\|((k-minn)%2)) {puts("NO");continue;}
	puts("YES");
	for(int i=1;i<=n;i++)
	{
	for(int j=1;j<m;j++)
	{
	if(i==1)
	{
	C1[i][j]=(cnt?'B':'R');
	cnt=!cnt;
	}
	else C1[i][j]='R';
	}
	}
	for(int i=1;i<n;i++)
	{
	for(int j=1;j<=m;j++)
	{
	if(j==m)
	{
	C2[i][j]=(cnt?'B':'R');
	cnt=!cnt;
	}
	else C2[i][j]='B';
	}
	}
	C1[2][1]='B',C1[n][m-1]=(cnt?'B':'R'),C1[n-1][m-1]=(cnt?'B':'R');
	C2[1][1]='R',C2[1][2]='R',C2[n-1][m-1]=C2[n-1][m];
	for(int i=1;i<=n;i++)
	{
	for(int j=1;j<m;j++) cout<<C1[i][j]<<" ";
	cout<<endl;
	}
	for(int i=1;i<n;i++)
	{
	for(int j=1;j<=m;j++) cout<<C2[i][j]<<" ";
	cout<<endl;
	}
	}
	return _123hh2;
	}

Construction