3762 二进制矩阵(思维题、构造)

1. 问题描述:

给定一个 n×m 大小的二进制矩阵,矩阵中只包含 0 和 1。现在,你可以进行如下操作:选中一个 2×2 的子矩阵,改变其中 3 个元素的值(0 变为 1,1 变为 0)。你的任务是通过上述操作,将矩阵中的全部元素都变为 0。你的总操作次数不得超过 3nm 次。可以证明,答案一定存在。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含整数 n,m。接下来 n 行,每行包含一个长度为 m 的 01 字符串,表示给定的二进制矩阵。

输出格式

每组数据第一行输出整数 k,表示操作次数,注意 k 的权值范围 [0,3nm]。接下来 k 行,每行包含 6 个整数 x1,y1,x2,y2,x3,y3,描述一次操作中选中的元素的坐标为 (x1,y1),(x2,y2),(x3,y3)。元素位置不能相同,且必须出自同一 2×2 子矩阵中。行列均从 1 开始计数,(1,1) 表示输入矩阵中位于左上角的元素,(n,m) 表示输入矩阵中位于右下角的元素。输出任意合理方案均可。

数据范围

1 ≤ t ≤ 5000,
2 ≤ n,m ≤ 100,
保证将同一测试点内的每组数据的 nm 相加一定不超过 20000。

输入样例:

5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

输出样例:

1
1 1 2 1 2 2

2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2
来源:https://www.acwing.com/problem/content/3765/

2. 思路分析:

我们每一次需要选择2 * 2的方格中的三个数字进行操作,最终需要使得矩阵中的元素全部变为0,输出在操作次数小于等于3nm下的每一次选择2 * 2矩阵中操作的三个元素的坐标,输出任意一种方案即可。首先我们需要挖掘一下题目中的一些性质,每一次我们可以按照"L"型来选择操作2 * 2方格中的三个元素,如下图所示:

3762 二进制矩阵(思维题、构造)

如上图所示可以发现存在四种"L"型的方案,我们可以按照0,1,2,3对每一种"L"型的操作进行编号,进一步可以发现对于矩阵中任意一个为1的元素我们都可以选择对应的2 * 2方格中的三个元素进行"L"型的操作使其变成1,并且其余元素不发生改变,而对于矩阵中任意一个为1的位置我们都可以执行相应的操作使其变为1,所以最终操作次数为矩阵中1的元素数目乘以3,并且我们还需要处理一下在边界上的1的问题,可以分为以下四种情况进行处,如果对应元素被操作三次那么这个要元素会发生改变,如果操作两次则不会发生改变:

3762 二进制矩阵(思维题、构造)

为了方便判断属于哪一种"L"型,我们可以按照"L"型的拐点的坐标传递到输出函数中这样可以执行相应的"L"型操作。

3. 代码如下:

class Solution:
    # k用来判断属于哪一种的"L"型的操作, PL用来输出当前类型为k下选择操作的三个坐标
    def PL(self, i: int, j: int, k: int):
        if k == 0:
            print(i, j, i + 1, j, i, j + 1)
        elif k == 1:
            print(i, j, i, j - 1, i + 1, j)
        elif k == 2:
            print(i, j, i - 1, j, i, j - 1)
        else:
            print(i, j, i - 1, j, i, j + 1)

    def process(self):
        T = int(input())
        # 总共有T组测试数据
        for i in range(T):
            # 矩阵的大小
            n, m = map(int, input().split())
            g = list()
            for j in range(n):
                # 需要将输入的每一行数据变为一个列表
                g.append(list(input()))
            # 求解需要操作的步数
            res = 0
            for j in range(n):
                for k in range(m):
                    if g[j][k] == "1":
                        res += 3
            print(res)
            for j in range(n):
                for k in range(m):
                    if g[j][k] == "1":
                        # 判断当前的位置属于哪一种情况
                        if j < n - 1 and k < m - 1:  # 不是最后一行或者是以后一列
                            # 注意下标是从1开始的所以在传递到PL函数之前全部先加上1
                            # 调用的时候根据图中四种类型传递坐标
                            self.PL(j + 1, k + 1, 0)
                            self.PL(j + 1, k + 1 + 1, 1)
                            self.PL(j + 1 + 1, k + 1, 3)
                        # 最后一列但是不包含最后一个格子
                        elif j < n - 1 and k == m - 1:
                            self.PL(j + 1, k + 1, 1)
                            self.PL(j + 1, k + 1 - 1, 0)
                            self.PL(j + 1 + 1, k + 1, 2)
                        # 最后一行但是不包含最后一个格子
                        elif k < m - 1 and j == n - 1:
                            self.PL(j + 1, k + 1, 3)
                            self.PL(j + 1, k + 1 + 1, 2)
                            self.PL(j + 1 - 1, k + 1, 0)
                        else:
                            # 最后一个格子
                            self.PL(j + 1, k + 1, 2)
                            self.PL(j + 1 - 1, k + 1, 1)
                            self.PL(j + 1, k + 1 - 1, 3)


if __name__ == '__main__':
    Solution().process()
上一篇:map的有关知识


下一篇:com.fasterxml.jackson.databind.exc.UnrecognizedPropertyException: Unrecognized field 异常