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

isdkz

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

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

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

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

下面是具体的代码实现：

1. def solve(n, m, grid):
   
2.     rows = [0] * n  # 记录每一行是否被涂色
   
3.     cols = [0] * m  # 记录每一列是否被涂色
   
4.     operations = []  # 记录操作序列
   
5. 
   
6.     for i in range(n):
   
7.         for j in range(m):
   
8.             if grid[ i][j] == 1 and rows[ i] == 0:
   
9.                 operations.append((1, i+1))
   
10.                 rows[ i] = 1
    
11.             elif grid[ i][j] == 0 and cols[j] == 0:
    
12.                 operations.append((2, j+1))
    
13.                 cols[j] = 1
    
14. 
    
15.     # 检查最终的网格图是否与目标状态一致
    
16.     for i in range(n):
    
17.         for j in range(m):
    
18.             if grid[ i][j] != 1 and rows[ i] == 0:
    
19.                 return -1
    
20.             if grid[ i][j] != 0 and cols[j] == 0:
    
21.                 return -1
    
22. 
    
23.     return operations
    
24. 
    
25. # 输入处理
    
26. n, m = map(int, input().split())
    
27. grid = []
    
28. for _ in range(n):
    
29.     row = list(map(int, input().split()))
    
30.     grid.append(row)
    
31. 
    
32. # 调用函数求解
    
33. result = solve(n, m, grid)
    
34. 
    
35. # 输出结果
    
36. if result == -1:
    
37.     print(-1)
    
38. else:
    
39.     print(len(result))
    
40.     for operation in result:
    
41.         print(operation[0], operation[1])
    

复制代码

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

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

希望能帮到你！