問題一覧 > 通常問題

No.3723 Climb or Detour

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 79
作問者 : 👑 kencho / テスター : 👑 p-adic uruzunyaa
お気に入りにしたユーザー ProblemId : 13566 / 自分の提出
問題文最終更新日: 2026-11-02 04:25:55
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$ grid with all cells painted white, and Alice is on it. Let $(i, j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left. Alice is currently at $(s_r, s_c)$.

Alice intends to reach her destination $(t_r, t_c)$ by repeatedly moving to a cell adjacent vertically or horizontally. However, Bob, who was watching this, has decided to play a prank by painting some cells black to make Alice take a detour.

Moving to a cell of the same color as the previous cell, such as white to white or black to black, takes $1$ unit of time, while moving to a cell of a different color from the previous cell, such as white to black or black to white, takes $2$ units of time.

Now, Bob can paint any number of cells of his choice black, except for Alice's current location and her destination. Which cells should he paint so that the minimum time Alice needs to travel from her current location to her destination is exactly $K$?

Figure this out on Bob's behalf. If no painting satisfies the condition, output -1.

Constraints

  • All input values are integers.
  • $2 \leq N \leq 1000$
  • $1 \leq K \leq 10^9$
  • $1 \leq s_r, s_c, t_r, t_c \leq N$
  • $(s_r, s_c) \neq (t_r, t_c)$

Input

The input is given from Standard Input in the following format.

$N\ K$
$s_r\ s_c$
$t_r\ t_c$

Output

If a painting satisfying the condition exists, output one such painting in the following format. Here, $S_i$ is a string of length $N$, and the $j$-th character of $S_i$ is # if the cell in the $i$-th row from the top and the $j$-th column from the left is painted black, and . if it is painted white.

If no painting satisfies the condition, output -1.

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

Print a newline at the end.

Visualizer

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

During the contest, sharing visualization results or discussing solutions or insights is prohibited. Please be careful.

In principle, questions about the visualizer's specifications will not be accepted. Please use it only as an auxiliary tool.

Sample

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

In the sample output, one example of a path with the minimum time is shown in the figure below: $(2, 1) \rightarrow (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (3, 5) \rightarrow (4, 5)$.

Sample 2
Input
2 3
1 1
2 2
Output
-1

Note that Alice's current location and destination cannot be painted black.

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