当前位置: 首页 > news >正文

The 3rd Universal Cup. Stage 23: Hong Kong

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

http://www.hskmm.com/?act=detail&tid=20322

相关文章:

  • 从0到1搭建高隐蔽性C2基础设施
  • RESTful风格
  • 软工9.27
  • 一些积分的题解
  • 2025 年超声波清洗机最新权威推荐排行榜:龙门式 / 悬挂式 / 全自动等多类型设备 TOP3 品牌深度解析与选购指南
  • 问题总结,软工9.28
  • 数据类型-字符串
  • 在AI技术唾手可得的时代,挖掘新需求成为制胜关键——某知名益智游戏框架需求探索
  • 详细介绍:零基础学AI大模型之LangChain六大核心模块与大模型IO交互链路
  • 基础组合计数与卢卡斯定理
  • 2025 最新中国过滤器品牌 TOP10 权威测评推荐厂家与选购指南
  • 2025 年东莞物流公司 TOP 物流服务推荐排行榜,东莞货运物流,东莞到全国物流,东莞大型设备物流,东莞到越南物流专线东莞大件物流,东莞整车物流公司推荐!
  • 使用Python网络爬虫抓取牛客网题目
  • 题解:洛谷 P1012 [NOIP 1998 提高组] 拼数
  • day 7
  • 完整教程:Python 高效实现 PDF 转 Word:告别手动复制粘贴
  • 深入解析:C# 串口通信全解析:从基础到复杂协议的设计思路
  • P6652 「SWTR-5」String
  • 模拟退火 - 学习笔记
  • Markdown语法入门一:标题,列表,表格与字体
  • 质数筛
  • pnpm 安装后无法使用
  • 数学解题中常见的“漏解”情况分析
  • 图册
  • 简单的Powershell脚本
  • 基于YOLO8+flask+layui的行人跌倒行为检测系统【源码+模型+数据集】 - 详解
  • 环形链表-leetcode
  • [ABC425C] Rotate and Sum Query 题解
  • 线程--基本使用、线程常用方法
  • 酵母表面展示技术:从蛋白分析到多领域应用,解锁可持续发展的生物新工具