Square Filling
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
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.
Input
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$.
Output
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.
3 3
1 1 1
1 1 1
0 1 1
3 3
1 0 1
1 0 1
0 0 0
3 2
0 0
0 0
0 0
3
1 1
1 2
2 2
-1
0
Note
The sequence of operations in the first example:
20240416集训
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2024-4-16 18:30
- End at
- 2024-4-16 21:00
- Duration
- 2.5 hour(s)
- Host
-
SamuelXuch
- Partic.
- 13