codeforces-scrape

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

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}$