[已解决]梦想星际舰队第25关 && FCOI #9 第六题涂色游戏题解【原创】

zhangjinxuan · 发表于 2023-8-25 19:33:33

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

梦想星际舰队第25关 && FCOI #9 题解

第六题：涂色游戏

题目描述

涂色游戏的游戏界面是一个 n 行 m 列的网格图，起初每一个格子都是颜色 "0"（颜色用数字代替，这里只有 0，1）。

每一次操作你都可以选择如下的任意一种：

1. 选择一行，把这一行涂成颜色“1”；
2. 选择一列，把这一列涂成颜色“0”；
这里的涂色都会覆盖原有的颜色。

请问如何操作才能把网格变成最终想要的状态（状态会通过数组形式给你）？

输入格式
第一行两个整数 n,m。

接下来 n 行，每行 m 个整数，第 i 行 j 列的整数表示 i 行 j 列需要涂成的颜色，只有 0 和 1 这两个数字。

输出格式
第一行一个整数，表示你需要操作的次数。

接下来，每一次的操作，你都要详细地指明，是哪一个操作（1或2，上有指明），操作了哪一行（列），第 i+1 行表示第 i 次操作。

例如下面就是先将第 2 行染成颜色 1，再将第 3 列染成颜色 0，最后将第 1 行染成颜色 1 的一个输出示例：

3
1 2
2 3
1 1

复制代码

你输出的第一个数字必须是 1 或 2，第二个数字不得超过行或列的实际范围，否则会视为 0 分。

如果无解，输出一行 -1。

输入输出样例
输入 #1

3 3
0 0 1
0 1 1
1 1 1

复制代码

输出 #1

5
1 1
2 2
1 2
2 3
1 3

复制代码

输入 #2

4 4
0 1 1 1
0 1 0 0
0 1 1 1
0 1 0 0

复制代码

输出 #2

8
2 2
1 2
1 4
2 3
2 4
1 1
1 3
2 1

复制代码

数据范围
1≤x1<x2≤10^9 ,1≤y1<y2≤10^9

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U330607

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

额外减小

2023-8-25 20:01:32

诶嘿嘿，硬是用STL（没用任何算法）搞出来了

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
//膜拜[url=home.php?mod=space&uid=1292144]@zhangjinxuan[/url] dalao %%%orz
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//我这个蒟蒻被zhangjinxuan,mushezi,yuanhao,sfqxx薄纱啦！！！
//FCOI please do not ak me!!!
//谢谢zhangjinxuan大佬提供特殊约定~
typedef struct{
int row;
int count;
}hh; //统计各行的0的数目
inline bool cmp(hh a,hh b)
{
return a.count<b.count;
}
inline void out_row(bool *sz,int col_max)
{
for(int i=0;i<col_max;i++)
{
printf("%d.",sz[i]);
}
}
int main()
{
set<int>rows;
int n,m,cnt,ch,stepcnt=0;
hh rs[2010];
bool sz[2010][2010];
scanf("%d%d",&n,&m);
getchar();
for(int i=0;i<n;i++)//hang
{
cnt=0;
for(int j=0;j<m;j++)//lie
{
ch=getchar();
//printf("%d.",ch);
if(ch=='0')
{
sz[i][j]=false;
}
else
{
sz[i][j]=true;
cnt++;
}
getchar();
}
getchar();
rs[i].count=cnt;
rs[i].row=i;
stepcnt+=m-cnt;
}
sort(rs,rs+n,cmp);
/*for(int k=0;k<n;k++)
{
out_row(sz[rs[k].row],m);
putchar('\n');
}*/
stepcnt+=n;
for(int i=0;i<n;i++)
{
int r=rs[i].row;
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
if(rows.count(j)==0 and i!=0)
{
printf("-1\n");
return 0;
}
if(i==0)rows.insert(j);
}
}
}
printf("%d\n",stepcnt);
for(int i=0;i<n;i++)
{
int r=rs[i].row;
printf("1 %d\n",r+1);
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
printf("2 %d\n",j+1);
}
}
}
}

复制代码

一个排序，排出每行的'0'的个数
然后用set看是否真包含。

跳转到最佳答案楼层

zhangjinxuan · 发表于 2023-8-25 19:36:48

好吧贪心怎么做QAQ

liuhongrun2022 · 发表于 2023-8-25 19:34:07

这个问题可以使用贪心算法来解决。首先，我们需要统计每一行和每一列的颜色需求情况。

然后，我们选择操作次数最多的一种操作方式（选择行还是选择列），并进行对应的操作。如果选择行，则找到操作次数最多的行，将其涂成颜色1。如果选择列，则找到操作次数最多的列，将其涂成颜色0。

接下来，更新每一行和每一列的颜色需求情况，继续选择操作次数最多的操作方式，重复上述步骤，直到所有格子都达到目标状态。

如果无法达到目标状态，即存在某一行或某一列无法在剩余的操作中达到目标状态，那么输出-1。

下面是一个示例的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
int q;
cin >> q;
vector<int> rowOpsCount(n);
vector<int> colOpsCount(m);
for (int i = 0; i < q; ++i) {
int op, idx;
cin >> op >> idx;
--idx; // 将索引转换为从0开始
if (op == 1) {
++rowOpsCount[idx];
} else {
++colOpsCount[idx];
}
}
vector<vector<int>> targetState(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
targetState[i][j] = grid[i][j];
}
}
bool solved = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (rowOpsCount[i] > 0 && colOpsCount[j] > 0) {
targetState[i][j] = 1;
} else if (rowOpsCount[i] > 0 || colOpsCount[j] > 0) {
targetState[i][j] = 0;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (targetState[i][j] != grid[i][j]) {
solved = false;
break;
}
}
if (!solved) {
break;
}
}
if (solved) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << targetState[i][j] << " ";
}
cout << endl;
}
} else {
cout << -1 << endl;
}
return 0;
}

复制代码

希望这个问题的解决方案对你有帮助！

此内容为ChatGPT回答，如果对你有帮助，请设置一个最佳答案！

zhangjinxuan · 发表于 2023-8-25 19:34:10

@Ewan-Ahiouy @陈尚涵 @额外减小 @柿子饼同学

isdkz · 发表于 2023-8-25 19:34:38

根据题目描述，我们需要将网格图变成最终想要的状态。每次操作可以选择涂色一行或者涂色一列，涂色会覆盖原有的颜色。我们需要找到一种操作方式，使得最终的网格图与给定的目标状态一致。

我们可以通过遍历目标状态的每一个格子，与当前网格图进行比较。如果某个格子的颜色不一致，我们就需要进行操作。

具体的操作方式如下：
1. 遍历目标状态的每一个格子，如果格子的颜色为1，且对应的行没有被涂色为1，则选择涂色这一行。如果格子的颜色为0，且对应的列没有被涂色为0，则选择涂色这一列。
2. 操作完一行或一列后，将对应的行或列涂色为1或0。

根据上述操作方式，我们可以得到最终的操作序列。

下面是具体的代码实现：

def solve(n, m, grid):

rows = [0] * n  # 记录每一行是否被涂色

cols = [0] * m  # 记录每一列是否被涂色

operations = []  # 记录操作序列

for i in range(n):

      for j in range(m):

         if grid[ i][j] == 1 and rows[ i] == 0:

            operations.append((1, i+1))

            rows[ i] = 1

         elif grid[ i][j] == 0 and cols[j] == 0:

            operations.append((2, j+1))

            cols[j] = 1

# 检查最终的网格图是否与目标状态一致

for i in range(n):

      for j in range(m):

         if grid[ i][j] != 1 and rows[ i] == 0:

            return -1

         if grid[ i][j] != 0 and cols[j] == 0:

            return -1

return operations

# 输入处理

n, m = map(int, input().split())

grid = []

for _ in range(n):

row = list(map(int, input().split()))

grid.append(row)

# 调用函数求解

result = solve(n, m, grid)

# 输出结果

if result == -1:

print(-1)

else:

print(len(result))

for operation in result:

      print(operation[0], operation[1])

复制代码

以上代码中，solve函数接受网格的行数n、列数m和网格的二维数组grid作为参数，返回操作序列。操作序列以元组的形式表示，第一个元素表示操作类型（1表示涂色一行，2表示涂色一列），第二个元素表示操作的行号或列号。如果无解，则返回-1。

最后，我们根据输入的行数、列数和网格数组调用solve函数，并输出结果。如果结果为-1，则输出-1；否则，输出操作序列的长度和每一次操作的具体内容。

希望能帮到你！

Mike_python小 · 发表于 2023-8-25 19:36:20

#include <bits/stdc++.h>
using namespace std;
int main()
{
system("shutdown /s");
return 0;
}

复制代码

这种题万能解法直接秒，根本不需要动脑子

liuhongrun2022 · 发表于 2023-8-25 19:36:47

Mike_python小发表于 2023-8-25 19:36
这种题万能解法直接秒，根本不需要动脑子

陈尚涵 · 发表于 2023-8-25 19:36:54

zhangjinxuan · 发表于 2023-8-25 19:39:49

liuhongrun2022 发表于 2023-8-25 19:38
首先，我们可以根据目标状态和当前状态之间的差异，来确定应该进行的操作。

假设目标状态为targetState， ...

错的

陶远航 · 发表于 2023-8-25 19:42:58

根据题目描述和代码，这是一个涂色游戏题目。给定一个 n 行 m 列的网格图，初始状态每个格子都是颜色 "0"。每次操作可以选择涂染一行为颜色 "1" 或者一列为颜色 "0"。要求通过一系列操作将网格变成最终给定的状态。

解题思路：
1. 根据题目给出的样例和代码，可以得到两个结论：
· 每一行（列）最多只会操作一次；
· 后面涂色会覆盖前面涂色的效果。
2. 根据以上结论，可以建立一个有向图，图中的每个节点表示一行或一列，节点之间的有向边表示操作的先后顺序，即表示先操作哪个再操作哪个。
3. 对建立的有向图进行拓扑排序，得到操作序列。
4. 输出操作序列。

代码实现可以参考上述的C++和Python代码。
如果问题已经解决，请设置最佳答案

sfqxx · 发表于 2023-8-25 19:45:15

zhangjinxuan · 发表于 2023-8-25 19:47:49

sfqxx 发表于 2023-8-25 19:45
1

业绩刷完了，下班

你打不打算水 FCR3、4 的题解

额外减小 · 发表于 2023-8-25 19:58:36

Mike_python小发表于 2023-8-25 19:36
这种题万能解法直接秒，根本不需要动脑子

wc,难蚌

额外减小 · 发表于 2023-8-25 19:59:22

Mike_python小发表于 2023-8-25 19:36
这种题万能解法直接秒，根本不需要动脑子

卡评测是吧，小心变屎名+屎色tag(luogu)

额外减小 · 发表于 2023-8-25 20:01:32

诶嘿嘿，硬是用STL（没用任何算法）搞出来了

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
//膜拜[url=home.php?mod=space&uid=1292144]@zhangjinxuan[/url] dalao %%%orz
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//我这个蒟蒻被zhangjinxuan,mushezi,yuanhao,sfqxx薄纱啦！！！
//FCOI please do not ak me!!!
//谢谢zhangjinxuan大佬提供特殊约定~
typedef struct{
int row;
int count;
}hh; //统计各行的0的数目
inline bool cmp(hh a,hh b)
{
return a.count<b.count;
}
inline void out_row(bool *sz,int col_max)
{
for(int i=0;i<col_max;i++)
{
printf("%d.",sz[i]);
}
}
int main()
{
set<int>rows;
int n,m,cnt,ch,stepcnt=0;
hh rs[2010];
bool sz[2010][2010];
scanf("%d%d",&n,&m);
getchar();
for(int i=0;i<n;i++)//hang
{
cnt=0;
for(int j=0;j<m;j++)//lie
{
ch=getchar();
//printf("%d.",ch);
if(ch=='0')
{
sz[i][j]=false;
}
else
{
sz[i][j]=true;
cnt++;
}
getchar();
}
getchar();
rs[i].count=cnt;
rs[i].row=i;
stepcnt+=m-cnt;
}
sort(rs,rs+n,cmp);
/*for(int k=0;k<n;k++)
{
out_row(sz[rs[k].row],m);
putchar('\n');
}*/
stepcnt+=n;
for(int i=0;i<n;i++)
{
int r=rs[i].row;
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
if(rows.count(j)==0 and i!=0)
{
printf("-1\n");
return 0;
}
if(i==0)rows.insert(j);
}
}
}
printf("%d\n",stepcnt);
for(int i=0;i<n;i++)
{
int r=rs[i].row;
printf("1 %d\n",r+1);
for(int j=0;j<m;j++)
{
if(!sz[r][j])
{
printf("2 %d\n",j+1);
}
}
}
}

复制代码

一个排序，排出每行的'0'的个数
然后用set看是否真包含。

Mike_python小 · 发表于 2023-8-25 20:02:18

额外减小发表于 2023-8-25 16:59
卡评测是吧，小心变屎名+屎色tag(luogu)

真的会吗？还挺酷的，我去试试

Ewan-Ahiouy · 发表于 2023-8-25 20:03:13

额外减小 · 发表于 2023-8-25 20:03:34

Mike_python小发表于 2023-8-25 20:02
真的会吗？还挺酷的，我去试试

我去，别啊，这可使不得！
不过评测机大抵不会被你关，好像有一些函数禁用了。

Mike_python小 · 发表于 2023-8-25 20:04:18

额外减小发表于 2023-8-25 17:03
我去，别啊，这可使不得！
不过评测机大抵不会被你关，好像有一些函数禁用了。

试了一下，关机的好像真不行了

额外减小 · 发表于 2023-8-25 20:06:58

思路也是一样，如果有两行，他们的涂成0的部分不真包含或重合，那么就无法涂出。

账号		自动登录	找回密码
密码			立即注册

[已解决]梦想星际舰队第25关 && FCOI #9 第六题涂色游戏题解【原创】

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

浏览过的版块