1207B.md (2317B)
1 Source: https://codeforces.com/problemset/problem/1207/B 2 3 B. Square Filling 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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 \lt n$ and $1 \le y \lt m$, and then set $B_{x, y}$, $B_{x, y + 1}$, $B_{x + 1, y}$ and $B_{x + 1, y + 1}$ to $1$. 24 25 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$. 26 27 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. 28 29 Input 30 31 The first line contains two integers $n$ and $m$ ($2 \le n, m \le 50$). 32 33 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$. 34 35 Output 36 37 If it is impossible to make $B$ equal to $A$, print one integer $-1$. 38 39 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. 40 41 Examples 42 43 Input 44 45 ``` 46 3 3 47 1 1 1 48 1 1 1 49 0 1 1 50 ``` 51 52 Output 53 54 ``` 55 3 56 1 1 57 1 2 58 2 2 59 ``` 60 61 Input 62 63 ``` 64 3 3 65 1 0 1 66 1 0 1 67 0 0 0 68 ``` 69 70 Output 71 72 ``` 73 -1 74 ``` 75 76 Input 77 78 ``` 79 3 2 80 0 0 81 0 0 82 0 0 83 ``` 84 85 Output 86 87 ``` 88 0 89 ``` 90 91 Note 92 93 The sequence of operations in the first example: 94 95 $\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}$