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

原题链接:

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. 传入的ij的值,应该是拐点的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;
}