L. Flipping Paths
题目链接：https://qoj.ac/contest/1885/problem/9926
题意：
给一个n * m 的网格，初始时有些格子是黑色的，有些是白色的，可以进行以下操作使得网格中所有的格子变成同一颜色（要求最多不超过400次）：
从左上角单元格（假设该单元格坐标为 ((1,1))）开始，并绘制一条到右下角单元格（坐标为 ((n,m))）的路径。路径必须沿着单元格，且只能向下或向右移动。具体来说，如果铅笔在 ((x,y))，它可以向下移动到 ((x+1,y))，或者向右移动到 ((x,y+1))。
之后，改变路径上所有单元格的颜色（即，将路径上所有白色单元格涂成黑色，所有黑色单元格涂成白色）。
题解：
每次操作尽可能多地修正当前行的 “错误颜色”。
对于当前行 i，从当前列 y 出发，向右走到该行最右侧的错误颜色格子 t。此过程中，每一步右移（'R'）都会翻转路径上的格子颜色，一次性修正 y 到 t 之间的错误（翻转后，原本错误的变为正确，原本正确的暂时变为错误，但后续操作会逐步处理）。
之后下移（'D'）到下一行，重复该逻辑；最后一行则持续右移到终点 ((n,m))。
然后对于目标颜色需要都枚举，白色的跑一次，黑色的跑一次。
然后题目中这个400次的过程没有很详细的含义，其实是代表着上述算法跑了超过400次可以证明这张图是无解的。
代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;#define debug(x) cout << "#x = " << x << endl;
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1061109567
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'const int N = 210;
int n, m;
char mp[N][N];
vector<char> ans[410]; // 存每次操作的路径
int num[N][N]; // 将字符转换为数字，便于改变bool work(char c)
{for (int i = 1; i <= 401; i++) ans[i].clear(); // 多测清空for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {num[i][j] = (mp[i][j] == c) ? 1 : 0; // 要改的标记为1}}for (int k = 1; k <= 401; k++) {bool all = true; // 是否已经全部变为同一颜色for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (num[i][j] != 0) all = false;}}if (all) {int cnt = k - 1; // 次数为本轮-1，即上一轮cout << "YES" << endl;cout << cnt << endl;for (int i = 1; i <= cnt; i++) {for (int j = 0; j < ans[i].size(); j++) {cout << ans[i][j];}cout << endl;}return true;}if (k > 400) return false; // 超过最大次数，无解int y = 1;for (int i = 1; i <= n; i++) {num[i][y] ^= 1; // 改变颜色int toal = 1; // 某一行的最右边的错误颜色for (int j = m; j >= 1; j--) {if (num[i][j] == 1) {toal = j;break;}}while (y < toal) { // 一直走到目标点y++;num[i][y] ^= 1;ans[k].push_back('R');}if (i < n) ans[k].push_back('D'); // 如果可以向下走else {while (y < m) { // 已经在第n行，继续向(n,m)走y++;num[n][y] ^= 1;ans[k].push_back('R');}}}}return false;}void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> mp[i][j];}}if (work('W') || work('B')) return; // 任意一个颜色满足即可cout << "NO" << endl; // 否则为NO}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
参考：https://blog.csdn.net/Zz_0913/article/details/145836558?fromshare=blogdetail&sharetype=blogdetail&sharerId=145836558&sharerefer=PC&sharesource=Jway3033&sharefrom=from_link