CF1898C Colorful Grid（构造）

题目链接

题目大意

n 行 m 列 的一个矩阵，每行有m - 1条边，每列有 n - 1 条边。
问一共走 k 条边，能不能从 （1， 1），走到（n， m），要求该路径上，每条边的颜色都是红蓝交替的，可以走重复的边。
输出YES/NO

思路

• NO的情况

  • 从起点到终点至少要走 n - 1 + m - 1步，若 k < n - 1 + m - 1, 则输出NO
  • 因为每绕一次路，都只能多走偶数步
    所以k - (n - 1 + m - 1)，是奇数时，NO

• 构造方法

  • 因为要红蓝交替，所以不能走回头路
  • 若k == n - 1 + m - 1，直接最短路弄成红蓝交替
  • 若k > n - 1 + m - 1，res = k - (n - 1 + m - 1)， res一定是偶数，偶数除以4，要不就能整除，要不就余2

    • 能被整除，就让它，绕着最后一圈转
      

    • 若余2，则先把这两步在开头时消耗掉，剩下的，绕着最后一圈转

    • 

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
char heng[N][N];
char shu[N][N];
void init()
{
	for (int i = 1; i < N; i ++ )
	{
		for (int j = 1; j < N; j ++ )
		{
			if (i % 2) shu[i][j] = 'R';
			else
			{
				shu[i][j] = 'B';
			}
			if (j % 2 == 0)
			{
				heng[i][j] = 'R';
			}
			else
			{
				heng[i][j] = 'B';
			}
		}
	}
}
int main()
{
	int T; cin >> T;
	while (T -- )
	{
		init();
		int n, m, k;
		cin >> n >> m >> k;
		int res = n - 1 + m - 1;
		if (res % 2 != k % 2 || k < res)
		{
			cout << "NO" << endl;
			continue;
		}
		
		if (heng[1][m - 1] == 'R')
		{
			shu[1][m] = 'B';
		}
		else
		{
			shu[1][m] = 'R';
		}
		for (int i = 2; i < n; i ++ )
		{
			if (shu[i - 1][m] == 'R')
			{
				shu[i][m] = 'B';
			}
			else
			{
				shu[i][m] = 'R';
			}
		}
		cout << "YES" << endl;
		int x = (k - res) % 4;
		if (x == 0)
		{
			if (shu[n - 1][m] == 'B')
			{
				shu[n - 1][m - 1] = 'B';
				heng[n][m - 1] = 'R';
				heng[n - 1][m - 1] = 'R';
			}
			if (shu[n - 1][m] == 'R')
			{
				shu[n - 1][m - 1] = 'R';
				heng[n][m - 1] = 'B';
				heng[n - 1][m - 1] = 'B';
			}
		}
		if (x == 2)
		{
			if (shu[n - 1][m] == 'B')
			{
				shu[n - 1][m - 1] = 'B';
				heng[n][m - 1] = 'R';
				heng[n - 1][m - 1] = 'R';
			}
			if (shu[n - 1][m] == 'R')
			{
				shu[n - 1][m - 1] = 'R';
				heng[n][m - 1] = 'B';
				heng[n - 1][m - 1] = 'B';
			}
			if (heng[1][2] == 'B')
			{
				shu[1][1] = 'R'; 
				shu[1][2] = 'R'; 
				heng[2][1] = 'B';
			}
			if (heng[1][2] == 'R')
			{
				shu[1][1] = 'B'; 
				shu[1][2] = 'B'; 
				heng[2][1] = 'R';
			}
		}
		for (int i = 1; i <= n; i ++ )
		{
			for (int j = 1; j < m; j ++ )
			{
				cout << heng[i][j] << " " ;
			}
			cout << endl;
		}
		for (int i = 1; i < n; i ++ )
		{
			for (int j = 1; j <= m; j ++ )
			{
				cout << shu[i][j] << " " ;
			}
			cout << endl;
		}
	}
	return 0;
}