codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/f2852edc25a48bf4fd9ec84f2f194ad481d4d4d0.png) 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  ![](https://espresso.codeforces.com/ec5f15b78d9ddedb6d1646c9175abfc425460384.png) 
    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.