C++每日一题-二进制矩阵-2！！！

63 阅读 0 评论 42 点赞

我是靠谱客的博主可耐钻石，最近开发中收集的这篇文章主要介绍C++每日一题-二进制矩阵-2！！！，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二进制矩阵
给定一个 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

讲一下这道题的具体做法

假设有一个3*3的矩阵里面分布着0或者1
在这里插入图片描述
我们要把任何位置上的 ‘1’ 变成 ‘0’ 可以把相对应的位置上变化三次，而需要变化的2*2矩阵里面的其他位置变化两次
总的来说就是用三次转换的机会把任何位置上的1 变成 0
举例：变化1，1坐标上的1为0 可以
在这里插入图片描述

如此变化三下，其他位置也有相对于的变化方式
像这种同时变化三个位置的方式一共有四种可以按照右下左下左上右上依次将其设为四个参数 0 1 2 3
生成一个方法需要传入变化的拐点坐标以及对应的变化方式
如下：
依次输出相对于的变化坐标

void PL(int i,int j,int m){
   if(m==0)printf("%d %d %d %d %d %dn",i,j,i+1,j,i,j+1);
   else if(m==1)printf("%d %d %d %d %d %dn",i,j,i+1,j,i,j-1);
   else if(m==2)printf("%d %d %d %d %d %dn",i,j,i,j-1,i-1,j);
   else if(m==3)printf("%d %d %d %d %d %dn",i,j,i-1,j,i,j+1);
}

其次就是一个位置需要怎样选择从四个变化里选择三个
非右下角坐标及右下边缘的：0 1 3 三种变化
右下角坐标的：2 1 3
右边缘的：1 0 2
下边缘的：3 0 2
代码如下：

  for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='1'){
                    if(i<n&&j<m)
                        PL(i,j,0),PL(i,j+1,1),PL(i+1,j,3);
                    else if(i==n&&j==m)
                       PL(i,j,2),PL(i-1,j,1),PL(i,j-1,3);
                    else if(i==n)
                    PL(i,j,3),PL(i-1,j,0),PL(i,j+1,2);
                    else if(j==m)
                    PL(i,j,1),PL(i+1,j,2),PL(i,j-1,0);
                    
                }
            }
        }

总答案如下：

#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int N=105;
char g[N][N];

int m,n,T;


void PL(int i,int j,int m){
   if(m==0)printf("%d %d %d %d %d %dn",i,j,i+1,j,i,j+1);
   else if(m==1)printf("%d %d %d %d %d %dn",i,j,i+1,j,i,j-1);
   else if(m==2)printf("%d %d %d %d %d %dn",i,j,i,j-1,i-1,j);
   else if(m==3)printf("%d %d %d %d %d %dn",i,j,i-1,j,i,j+1);
}
int main(){
    cin>>T;
    while(T--){
        int res=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
        //g[i]+1表示从g[i][1]个位置开始输入字符串
            cin>>g[i]+1;
              for(int j=1;j<=m;j++){
                if(g[i][j]=='1'){
                    res+=3;
                }
            }
        }
        cout<<res<<endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='1'){
                    if(i<n&&j<m)
                        PL(i,j,0),PL(i,j+1,1),PL(i+1,j,3);
                    else if(i==n&&j==m)
                       PL(i,j,2),PL(i-1,j,1),PL(i,j-1,3);
                    else if(i==n)
                    PL(i,j,3),PL(i-1,j,0),PL(i,j+1,2);
                    else if(j==m)
                    PL(i,j,1),PL(i+1,j,2),PL(i,j-1,0);
                    
                }
            }
        }
    }
    return 0;
    
}