問題一覧 > 通常問題

No.2824 Lights Up! (Grid Edition)

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 17
作問者 : みどりむし🦠 / テスター : FplusFplusF viral8 achapi 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10818 / 自分の提出
問題文最終更新日: 2024-07-29 14:09:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 438 (順位表) の他の問題:

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.

Operation $(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.

Action $(r,c) \scriptsize \; (0 \leq r, c < N)$ is as follows:

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 -1 on 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
Sample Input/Output 4
Input
3
###
#.#
###
Output
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。