No.2824 Lights Up! (Grid Edition)
タグ : / 解いたユーザー数 17
作問者 :
みどりむし🦠
/ テスター :
FplusFplusF
Problem Statement
There is a grid with $N$ cells vertically and horizontally, consisting of $N^2$ cells in total.
For $2$ integers $r, c$, "cell $(r, c)$" denotes the cell in the $r \bmod N$-th row from the top and the $c \bmod N$-th column from the left.
Here, "$x \bmod N$" is the unique integer $r$ such that there exists an integer $q$ with $x = Nq + r$ and $0 \leq r < N$ holds.$\scriptsize \; (x \in \Z)$
Initially, cell $(r, c) \scriptsize \; (0 \leq r, c < N)$ is painted white if $S_{r, c} =$ ., and black if $S_{r, c} =$ #.
There are $N^2$ kinds each of operations and actions.
They are distinguished as "operation $(r, c)$"$\scriptsize \; (0 \leq r, c < N)$ and "action $(r, c) $"$\scriptsize (0 \leq r, c < N)$, respectively.
Action $(r,c) \scriptsize \; (0 \leq r, c < N)$ is as follows:Flip the colors of $4$ cells, namely cells $(r, c), (r - 1, c), (r, c - 1), (r - 1, c - 1)$, in this order. (A black cell is repainted white, and a white cell is repainted black.)
Note that, depending on the value of $N$, the color of the same cell may be flipped multiple times.
Perform $3$ operations, namely operations $(r, c), (r, 0), (0, c)$, in this order.
Note that, depending on the values of $r, c$, the same operation may be performed multiple times.
Uni can perform these actions in any order, at least $0$ and at most $N^2$ times in total.
Uni's goal is to have all cells painted white.
Determine whether this goal can be achieved, and if it can, find $1$ such procedure.
Example for $N = 8$:
From left to right, the figures show the cells flipped (an odd number of times) by actions $(4, 5), (1, 1), (0, 5)$.
Input
The input is given from standard input in the following format:
$N$
$S_{1,1}S_{1,2}\dots S_{1,N}$
$S_{2,1}S_{2,2}\dots S_{2,N}$
$\vdots$
$S_{N,1}S_{N,2}\dots S_{N,N}$
Output
Output the answer to standard output according to the following instructions:
- If the goal cannot be achieved: output
-1on one line. - If the goal can be achieved:
- Let the non-negative integer $T \; (T \leq N^2)$ be the length of the procedure in your answer (the number of actions).
- Output $T$ pairs of integers $(R_1, C_1), (R_2, C_2), \dots, (R_T, C_T)$, each a $2$-tuple, such that the $i \scriptsize \; (1 \leq i \leq T)$-th action is action $(R_i, C_i) \scriptsize \; (0 \leq R_i, C_i < N)$, together with $T$, in the following format:
$T$ $R_1 \enspace C_1$ $R_2 \enspace C_2$ $\vdots$ $R_T \enspace C_T$
Constraints
- $1 \leq N \leq 10^\bold{3}$
- $N$ is an integer
- $S_{i,j} \in \{$
.$, $#$\} \scriptsize \; (1 \leq i, j \leq N)$
Sample
Sample Input/Output 1
Input
7 ..#.#.. ....... #.##..# ..#.#.. #..##.# ....... ..#.#..
Sample Output
2 3 3 4 4
- First, performing action $(3, 3)$ makes the grid as follows:
...##.. ....... ....... #..##.# #..##.# ....... ...##..
- Next, additionally performing action $(4, 4)$ makes the grid as follows:
....... ....... ....... ....... ....... .......
Sample Input/Output 2
Input
5 #...# .#..# ..... ..... ##...
Sample Output
1 1 1
Sample Input/Output 3
Input
6
#.##.#
...#.#
.####.
##..##
##..##
##.##.
Sample Output
8
1 5
4 3
0 0
2 4
4 4
0 2
3 2
5 2
Input
6 #.##.# ...#.# .####. ##..## ##..## ##.##.
Sample Output
8 1 5 4 3 0 0 2 4 4 4 0 2 3 2 5 2
Sample Input/Output 4
Input
3 ### #.# ###
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。