Square Filling

1000ms

262144K

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.

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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

-1

Sample Input:

Sample Output:

Note:

The sequence of operations in the first example:

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

Informação

Provedor Codeforces

Código CF1207B