3762. 二进制矩阵原题链接

62 阅读 0 评论 41 点赞

我是靠谱客的博主坚强丝袜，最近开发中收集的这篇文章主要介绍3762. 二进制矩阵原题链接，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接

给定一个 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
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

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 105;

int n, m;
char num[N][N];

void PL(int i, int j, int type)
{
    switch(type)
    {
    case 0://左上角为枢纽
        printf("%d %d %d %d %d %dn",i,j,i,j+1,i+1,j);
        break;
    case 1://右上角为枢纽
        printf("%d %d %d %d %d %dn",i,j-1, i,j, i+1, j);
        break;
    case 2://左下角为枢纽
        printf("%d %d %d %d %d %dn",i-1,j, i, j, i, j+1);
        break;
    case 3://右下角为枢纽
        printf("%d %d %d %d %d %dn",i-1,j, i,j-1, i,j);
        break;
    }
}

int main()
{
    int T, i, j;
    cin>>T;
    while (T--)
    {
        cin>>n>>m;//输入字符
        for (i = 1; i <= n; i++)
            cin>>num[i]+1;


        int ans = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                if (num[i][j] == '1')//统计字符中字符1的个数
                    ans+=3;//将2*2矩阵中的每个字符1改变成字符0而不改变其他位置的字符，有一种方案是将当前位置变换三次而其他位置仅变换两次，需要操作三个位置
        cout<<ans<<endl;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                if(num[i][j] == '1')//把字符1变成字符0，字符1的位置存在4种情况
                {
                    if (i < n && j < m)//不在最后一行也不在最后一列
                    {
                        PL(i,j,0);//改变以(i,j)为枢纽的左上角，即输出(i,j),(i,j+1),(i+1,j)
                        PL(i,j+1,1);//改变以(i,j+1)为枢纽的右上角，即输出(i,j),(i,j+1),(i+1,j+1)
                        PL(i+1,j,2);//改变以(i+1,j)为枢纽的左下角，即输出(i,j),(i+1,j),(i+1,j+1)
                    }
                    else if (i == n && j < m)//在最后一行但不在最后一列
                    {
                        PL(i-1,j,0);
                        PL(i,j,2);
                        PL(i,j+1,3);
                    }
                    else if (i < n && j == m)//在最后一列但不在最后一行
                    {
                        PL(i,j-1,0);
                        PL(i,j,1);
                        PL(i+1,j,3);
                    }
                    else if (i == n && j == m)//在最后一行最后一列
                    {
                        PL(i-1,j,1);
                        PL(i,j-1,2);
                        PL(i,j,3);
                    }
                }
    }
    return 0;
}