CF1898C Colorful Grid（构造）

本文主要是介绍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;
}