Square Filling

题意翻译

给定一个全零的$n×m$矩阵，每次可以选定一个点$(x,y)|1≤x<n,1≤y<m$，把$(x,y)(x+1,y)(x,y+1)(x+1,y+1)$均改成$1$，求一个操作序列把这个全零矩阵转化为目标矩阵，你不必最小化步骤 $2≤n,m≤50$，所以你的操作数量最多为$2500$ 输入$n,m$和该目标矩阵，若不存在合法方案，输出$-1$ 否则先输出操作数量，然后每行输出$(x_i,y_i)$，表示本次操作选中$(x,y)$

题目描述

You are given two matrices $ A $ and $ B $ . Each matrix contains exactly $ n $ rows and $ m $ columns. Each element of $ A $ is either $ 0 $ or $ 1 $ ; each element of $ B $ is initially $ 0 $ . You may perform some operations with matrix $ B $ . During each operation, you choose any submatrix of $ B $ having size $ 2 \times 2 $ , and replace every element in the chosen submatrix with $ 1 $ . In other words, you choose two integers $ x $ and $ y $ such that $ 1 \le x < n $ and $ 1 \le y < m $ , and then set $ B_{x, y} $ , $ B_{x, y + 1} $ , $ B_{x + 1, y} $ and $ B_{x + 1, y + 1} $ to $ 1 $ . Your goal is to make matrix $ B $ equal to matrix $ A $ . Two matrices $ A $ and $ B $ are equal if and only if every element of matrix $ A $ is equal to the corresponding element of matrix $ B $ . Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes $ B $ equal to $ A $ . Note that you don't have to minimize the number of operations.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n, m \le 50 $ ). Then $ n $ lines follow, each containing $ m $ integers. The $ j $ -th integer in the $ i $ -th line is $ A_{i, j} $ . Each integer is either $ 0 $ or $ 1 $ .

输出格式

If it is impossible to make $ B $ equal to $ A $ , print one integer $ -1 $ . Otherwise, print any sequence of operations that transforms $ B $ into $ A $ in the following format: the first line should contain one integer $ k $ — the number of operations, and then $ k $ lines should follow, each line containing two integers $ x $ and $ y $ for the corresponding operation (set $ B_{x, y} $ , $ B_{x, y + 1} $ , $ B_{x + 1, y} $ and $ B_{x + 1, y + 1} $ to $ 1 $ ). The condition $ 0 \le k \le 2500 $ should hold.

输入输出样例

输入样例 #1

3 3
1 1 1
1 1 1
0 1 1

输出样例 #1

3
1 1
1 2
2 2

输入样例 #2

3 3
1 0 1
1 0 1
0 0 0

输出样例 #2

-1

输入样例 #3

3 2
0 0
0 0
0 0

输出样例 #3

0

说明

The sequence of operations in the first example: $ \begin{matrix} 0 & 0 & 0 & & 1 & 1 & 0 & & 1 & 1 & 1 & & 1 & 1 & 1 \\ 0 & 0 & 0 & \rightarrow & 1 & 1 & 0 & \rightarrow & 1 & 1 & 1 & \rightarrow & 1 & 1 & 1 \\ 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 1 & 1 \end{matrix} $