問題一覧 > 通常問題

No.3742 Re: Verse X

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 10
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13742 / 自分の提出
問題文最終更新日: 2026-11-02 04:29:47
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
グリッド構築24題 (順位表) の他の問題:

Problem Statement

There is an $N \times N$ square grid. Initially, each cell is painted white or black.

Is it possible to make all cells white by performing the following operation between $0$ and $5 \times 10^5$ times, inclusive? If it is possible, output one example of such a sequence of operations; otherwise, output -1.

  • Choose a square subgrid whose side length is an odd number of cells, at least $3$, and flip the colors of all cells on the diagonals of the square subgrid.
    • More formally, choose one integer triple $(k, r, c)$ satisfying all of $k \geq 1, k + 1 \leq r \leq N - k, k + 1 \leq c \leq N - k$, and flip the colors of the $4k+1$ cells that can be represented as $(r + i, c + i)$ or $(r + i, c - i)$ using an integer $i\ (-k \leq i \leq k)$.

Constraints

  • $3 \leq N \leq 500$
  • $S_i$ is a string of length $N$ consisting only of . and #

Input

The input is given from standard input in the following format.

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

The cell in the $i$-th row from the top and the $j$-th column from the left of the grid is painted white if the $j$-th character of $S_i$ is ., and black if it is #.

Output

Output one example of a sequence of operations in the following format.

$T$
$k_1\ r_1\ c_1$
$k_2\ r_2\ c_2$
$\vdots$
$k_T\ r_T\ c_T$

Here, the variables have the following meanings.

  • $T$ is an integer between $0$ and $5 \times 10^5$, inclusive, representing the length of the sequence of operations
  • $k_i, r_i, c_i$ are the values of $k, r, c$ chosen in the $i$-th operation

If no sequence of operations satisfying the conditions exists, output -1.

Print a newline at the end.

Visualizer

A web-based visualizer for the output is available here.

During the contest, sharing visualization results and mentioning solutions or analysis are prohibited. Please be careful.

In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
5
..#.#
...#.
##.#.
.###.
##.##
Output
3
1 2 2
1 4 3
2 3 3

The state of the grid changes as shown in the figure below.

Sample 2
Input
3
.#.
..#
.#.
Output
-1

Note that operations that extend outside the grid are not allowed.

Sample 3
Input
15
...............
.....#####.....
...#########...
.#############.
#..#########..#
###..#####..###
#####..#..#####
#..####.#######
###..##.#######
#######.#######
#######.#######
#######.#######
.######.######.
...####.####...
.....##.##.....
Output
66
1 12 6
1 13 11
1 5 2
1 14 4
1 6 9
1 14 13
1 11 2
3 8 11
1 6 13
2 6 3
1 4 11
1 5 8
2 3 5
4 11 10
4 9 11
1 10 4
1 10 13
1 3 6
2 4 3
1 4 6
2 8 3
1 8 5
1 12 2
1 12 8
2 3 9
2 4 6
1 14 11
4 6 5
1 11 11
3 12 4
5 8 6
3 7 8
1 11 7
1 10 6
2 8 4
1 9 9
1 11 14
1 12 3
1 2 2
1 14 10
1 11 4
1 5 5
1 3 11
2 9 4
1 7 8
1 10 5
4 11 7
1 12 14
1 9 10
1 11 13
1 5 12
1 12 4
2 7 4
1 8 14
1 7 12
3 4 12
1 6 14
1 7 14
2 13 3
1 9 6
1 7 3
2 9 3
2 3 13
2 7 3
4 5 5
2 12 7

The input grid is as follows.

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