二进制矩阵（秋季每日一题 2）

给定一个 $n\times m$ 大小的二进制矩阵，矩阵中只包含 $0$ 和 $1$。

现在，你可以进行如下操作：选中一个 $2\times 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\times 2$ 子矩阵中。

行列均从 $1$ 开始计数，$(1,1)$ 表示输入矩阵中位于左上角的元素，$(n,m)$ 表示输入矩阵中位于右下角的元素。

输出任意合理方案均可。

数据范围
$1\le t\le 5000,$
$2\le n,m\le 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

输出样例：

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

每次 $L$ 操作可以改变 $3$ 个位置的值
对每个位置的 $1$，都可以通过 $3$ 次 $L$ 操作改变其值，而不改变矩阵中其它位置的值，所以只需要 $3$ $\ast$ ($1$ 的个数) 次 $L$ 操作，就可以让全部的 $1$ 变为 $0$，而不改变原来的 $0$ 的值。

#include

using namespace std;

const int N = 110;

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

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

int main(){
    
    int t;
    cin >> t;
    
    while(t--){
        
        cin >> n >> m;
        
        for(int i = 1; i <= n; i++)
            cin >> g[i] + 1;
        
        int res = 0;
        for(int i = 1; i <= n; i++)
            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, 2), pl(i, j+1, 3), pl(i+1, j, 1);
                    }else if(i == n && j == m){
                        pl(i, j, 4), pl(i, j-1, 1), pl(i-1,j, 3);
                    }else if(i == n){
                        pl(i, j, 1), pl(i-1, j,2), pl(i, j+1, 4);
                    }else {
                        pl(i, j, 3), pl(i+1, j, 4), pl(i, j-1, 2);
                    }
                }
        
    }
    
    return 0;
}
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
53
54
55