[Solution] Big Brush solution codeforces

Big Brush solution codeforces – You found a painting on a canvas of size 𝑛×𝑚n×m. The canvas can be represented as a grid with 𝑛n rows and 𝑚m columns. Each cell has some color. Cell (𝑖,𝑗)(i,j) has color 𝑐𝑖,𝑗ci,j.

Near the painting you also found a brush in the shape of a 2×22×2 square, so the canvas was surely painted in the following way: initially, no cell was painted. Then, the following painting operation has been performed some number of times:

  • Choose two integers 𝑖i and 𝑗j (1𝑖<𝑛1≤i<n1𝑗<𝑚1≤j<m) and some color 𝑘k (1𝑘𝑛𝑚1≤k≤nm).
  • Paint cells (𝑖,𝑗)(i,j)(𝑖+1,𝑗)(i+1,j)(𝑖,𝑗+1)(i,j+1)(𝑖+1,𝑗+1)(i+1,j+1) in color 𝑘k.

All cells must be painted at least once. A cell can be painted multiple times. In this case, its final color will be the last one.

Find any sequence of at most 𝑛𝑚nm operations that could have led to the painting you found or state that it’s impossible.

Big Brush solution codeforces

The first line of input contains two integers 𝑛n and 𝑚m (2𝑛,𝑚10002≤n,m≤1000) — the dimensions of the canvas.

On the 𝑖i-th of the next 𝑛n lines of input, there will be 𝑚m integers. The 𝑗j-th of them is 𝑎𝑖,𝑗ai,j (1𝑎𝑖,𝑗𝑛𝑚1≤ai,j≤nm) — the color of cell (𝑖,𝑗)(i,j).

Output

If there is no solution, print a single integer 1−1.

Otherwise, on the first line, print one integer 𝑞q (1𝑞𝑛𝑚1≤q≤nm) — the number of operations.

Next, print the operations in order. On the 𝑘k-th of the next 𝑞q lines, print three integers 𝑖i𝑗j𝑐c (1𝑖<𝑛1≤i<n1𝑗<𝑚1≤j<m1𝑐𝑛𝑚1≤c≤nm) — the description of the 𝑘k-th operation.

If there are multiple solutions, print any.

Big Brush solution codeforces

4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4
output

Copy
6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2
input

Copy
3 4
1 1 1 1
2 2 3 1
2 2 1 1
output

Copy
-1

Big Brush solution codeforces

In the first test case, the solution is not unique. Here’s one of them:

Big Brush solution codeforces
In the second test case, there is no way one could obtain the given painting, thus the answer is 1−1.

 

Leave a Comment