1647C.md (2970B)
1 Source: https://codeforces.com/problemset/problem/1647/C 2 3 C. Madoka and Childish Pranks 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 Madoka as a child was an extremely capricious girl, and one of her favorite pranks was drawing on her wall. According to Madoka's memories, the wall was a table of $n$ rows and $m$ columns, consisting only of zeroes and ones. The coordinate of the cell in the $i$-th row and the $j$-th column ($1 \le i \le n$, $1 \le j \le m$) is $(i, j)$. 22 23 One day she saw a picture "Mahou Shoujo Madoka Magica" and decided to draw it on her wall. Initially, the Madoka's table is a table of size $n \times m$ filled with zeroes. Then she applies the following operation any number of times: 24 25 Madoka selects any rectangular subtable of the table and paints it in a chess coloring (the upper left corner of the subtable always has the color $0$). Note that some cells may be colored several times. In this case, the final color of the cell is equal to the color obtained during the last repainting. 26 27  White color means $0$, black means $1$. So, for example, the table in the first picture is painted in a chess coloring, and the others are not. 28 29 For better understanding of the statement, we recommend you to read the explanation of the first test. 30 31 Help Madoka and find some sequence of no more than $n \cdot m$ operations that allows you to obtain the picture she wants, or determine that this is impossible. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10$) — the number of test cases. Description of the test cases follows. 36 37 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 100$) — the size of the table. Each of the following $n$ lines contains a string of length $m$ consisting only of $1$ and $0$ — description of the picture that Madoka wants to obtain. 38 39 Output 40 41 If it is impossible to obtain the given picture, print $-1$. 42 43 Otherwise, print in the first line a single integer $q$ ($0 \leq q \leq n \cdot m$) — the number of operations you need to obtain the picture. Note that you do not need to minimize the number of operations. 44 45 Then for each operation (in the order of execution) print a single line containing four numbers — the coordinates of the upper-left corner and the lower-right corner of the rectangle. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 4 5 55 56 01000 57 58 10100 59 60 01010 61 62 00110 63 64 2 3 65 66 001 67 68 010 69 70 3 3 71 72 110 73 74 101 75 76 000 77 78 1 1 79 80 0 81 ``` 82 83 Output 84 85 ``` 86 4 87 1 1 3 3 88 3 3 4 4 89 4 3 4 4 90 4 2 4 3 91 1 92 1 2 2 3 93 -1 94 0 95 ``` 96 97 Note 98 99 The description of the first test case is below. 100 101  102 103 In the third test case, it is impossible to paint the desired picture. 104 105 In the fourth test case, the initial table is already the desired picture.