CF1898C Colorful Grid

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;
}