【二进制矩阵】ACwing 暑假每日一题

本文最后更新于：2021年8月18日下午1点45分

原题链接：

3762. 二进制矩阵 - AcWing题库

解析：

修改元素方法：

题目中给了以下这段话

image-20210712205256855

想要证明这个答案一定存在，方法是：

对于一个2X2的矩阵，如下图

image-20210712210012298

我们进行如图所示的编号

当我们用题目所描述的方法：**选中一个 2×2 的子矩阵，改变其中 3 个元素的值（00 变为 11，11 变为 00） **

修改①号元素方法如下：（按照 a , b , c 的顺序改变3个元素的值

image-20210712210207572

可以看到，①号位置的元素被修改了3次，其余②③④位置的元素被修改了两次

最终只有①号位置的元素被修改，因此总操作数最多为数据量的3倍，即：3mn

姑且叫这种方法叫做：3L变换（即通过3次L型变换修改其中的数据

同理：修改②号元素的方法为：

image-20210712211556699

自定义L型方向：

image-20210712212245876

特判：

转自AcWing 3762. 二进制矩阵 - AcWing

image-20210712212044927

相同的颜色可以对应同一种变换方式，只需要分四种情况讨论即可：

  1. 红色对应 i<n 且 j=1：选择以该点为左上角的矩阵
  2. 绿色对应 i=1 且 j>1：选择以该点为右上角的矩阵
  3. 黄色对应 i=n 且 j<m：选择以该点为左下角的矩阵
  4. 蓝色对应 i>1 且 j=m：选择以该点为右下角的矩阵

注意：

  1. 注意特判
  2. 传入的i和j的值，应该是拐点的IO坐标
  3. 注意读取二维数组读取字符的时候，scanf("%s",a[i] + 1);，其中这里的+1是代表从a[i][1]开始放字符串，因为这题数组下标是从1开始的，例如传入10010，那么a[i][1]=1 a[i][2]=0 a[i][3]=0 a[i][4]=1 a[i][5]=0
  4. 这题只要输出一种可能情况即可

AC源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>

using namespace std;

void f( int i , int j , int k)
{
    if ( k == 0) printf("%d %d %d %d %d %d\n", i , j , i + 1 , j ,i , j + 1 );
    if ( k == 1) printf("%d %d %d %d %d %d\n", i , j , i , j - 1  , i + 1 , j );
    if ( k == 2) printf("%d %d %d %d %d %d\n", i , j , i , j - 1 , i - 1  , j  );
    if ( k == 3) printf("%d %d %d %d %d %d\n", i , j , i - 1 , j , i  , j + 1);
}

int main()
{
    char a[110][110];
    int T;
    cin >> T;
    while ( T --)
    {
        int n, m , res = 0;
        cin >> n >> m;
        for ( int i = 1 ; i <= n ; i ++)
        {
            scanf("%s",a[i] + 1);
            for ( int j = 1 ; j <= m ; j ++)
            {
                if ( a[i][j] == '1') res += 3;
            }
        }
        cout << res << endl;
        for ( int i = 1 ; i <= n ; i ++)
        {
            for ( int j = 1 ; j <= m ; j ++)
            {
                if ( a[i][j] == '1')
                {
                    if ( i < n && j == 1)
                        f( i , j , 0 ) , f( i , j + 1 , 1) , f( i + 1 , j , 3);
                    else if ( i == 1 && j > 1)
                        f( i , j , 1 ) , f( i , j - 1 , 0) , f( i + 1, j , 2);
                    else if ( i == n && j < m)
                        f( i , j , 3) , f( i - 1 , j , 0) , f( i , j + 1 , 2);
                    else if ( i > 1 && j == m)
                        f( i  , j  , 2) , f( i - 1 , j ,1 ) , f( i , j - 1 , 3);
                    else 
                        f( i , j , 0 ) , f( i , j + 1 , 1) , f( i + 1 , j , 3);
                }
            }
        }
    }
    return 0;
}