Skip to content
Sign in

迷路 (Maze)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
2048 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

迷路を解くのが好きな K 理事長は，迷路になりそうなマス目を見つけた．マス目は縦 \(R\) 行，横 \(C\) 列の長方形の形をしており，各マスは白または黒で塗られている．上から \(i\) 行目 (\(1 \leqq i \leqq R\))，左から \(j\) 列目 (\(1 \leqq j \leqq C\)) のマスをマス \((i, j)\) と呼ぶことにする．

K 理事長は，マス目の白いマスは通れるマス，黒いマスは通れないマスとして，迷路を解くことにした．具体的には，以下のようにして迷路を解く．

  1. 白いマスの中からスタートのマス \((S_r, S_c)\) とゴールのマス \((G_r, G_c)\) を選ぶ．
  2. 上下左右に隣接する白いマスに移動することを繰り返して，スタートのマスからゴールのマスへ移動する経路を見つける．

K 理事長はスタートのマスとゴールのマスを決めたが，マス目の色の塗られ方によっては，白いマスのみを通ってスタートからゴールへ移動する経路が存在しない場合があることに気がついた．そこで， K 理事長の持っている \(N \times N\) マスの大きさのハンコを用いて以下の操作を繰り返すことで，スタートからゴールへ移動する経路が存在するようにしたい．

操作：マス目から \(N \times N\) マスの正方形の領域を選び，この領域に含まれるマスをすべて白にする．より厳密には，\(1 \leqq a \leqq R - N + 1\)，\(1 \leqq b \leqq C - N + 1\) を満たす整数 \(a, b\) を選び，\(a \leqq i \leqq a + N - 1\)，\(b \leqq j \leqq b + N - 1\) を満たすすべての整数の組 \((i, j)\) に対して，マス \((i, j)\) を白にする．

ハンコを使うと手が汚れる可能性があるため，操作回数はできるだけ少なくしたい．マス目の塗られ方とハンコの大きさ，スタートのマスとゴールのマスが与えられたとき，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための，操作回数の最小値を求めるプログラムを作成せよ．

Input

入力は以下の形式で標準入力から与えられる．

\(R\) \(C\) \(N\)
\(S_r\) \(S_c\)
\(G_r\) \(G_c\)
\(A_1\)
\(A_2\)
\(\vdots\)
\(A_R\)

\(A_i\) (\(1 \leqq i \leqq R\)) は . または # からなる長さ \(C\) の文字列である．\(A_i\) の \(j\) 文字目 (\(1 \leqq j \leqq C\)) はマス \((i, j)\) の色を表し，. はそのマスの色が白であることを，# はそのマスの色が黒であることを表す．

Output

標準出力に，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための操作回数の最小値を \(1\) 行で出力せよ．

Constraints

  • \(1 \leqq N \leqq R \leqq C\)．
  • \(R \times C \leqq 6\,000\,000\)．
  • \(1 \leqq S_r \leqq R\)．
  • \(1 \leqq S_c \leqq C\)．
  • \(1 \leqq G_r \leqq R\)．
  • \(1 \leqq G_c \leqq C\)．
  • \((S_r, S_c) \neq (G_r, G_c)\)．
  • \(A_i\) (\(1 \leqq i \leqq R\)) は . または # からなる長さ \(C\) の文字列である．
  • マス \((S_r, S_c)\) の色は白である．
  • マス \((G_r, G_c)\) の色は白である．
  • \(R, C, N, S_r, S_c, G_r, G_c\) は整数である．

Subtasks

  1. (\(8\) 点) \(N = 1\)，\(R \times C \leqq 1\,500\,000\)．
  2. (\(19\) 点) \(R \times C \leqq 1\,000\)．
  3. (\(16\) 点) 答えは \(10\) 以下である，\(R \times C \leqq 1\,500\,000\)．
  4. (\(19\) 点) \(R \times C \leqq 60\,000\)．
  5. (\(5\) 点) \(R \times C \leqq 150\,000\)．
  6. (\(19\) 点) \(R \times C \leqq 1\,500\,000\)．
  7. (\(8\) 点) \(R \times C \leqq 3\,000\,000\)．
  8. (\(6\) 点) 追加の制約はない．

Examples

Sample input 1
2 4 2
1 1
2 4
.###
###.
Sample output 1
1

\((a, b) = (1, 2)\) を選んで \(1\) 回操作を行い，マス \((1, 2), (1, 3), (2, 2), (2, 3)\) を白にすると，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようになる．例えば，経路 \((1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4)\) はその \(1\) つである．

操作を \(1\) 回も行わない場合，白いマスのみを通ってスタートからゴールへ移動する経路は存在しないから，\(1\) を出力する．

この入力例は小課題 \(2, 3, 4, 5, 6, 7, 8\) の制約を満たす．

Sample input 2
6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###
Sample output 2
4

この入力例はすべての小課題の制約を満たす．

Sample input 3
6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.
Sample output 3
1

この入力例は小課題 \(2, 3, 4, 5, 6, 7, 8\) の制約を満たす．

Sample input 4
1 15 1
1 15
1 1
...............
Sample output 4
0

操作を \(1\) 回も行わなくても，白いマスのみを通ってスタートからゴールへ移動する経路が存在する場合がある．

この入力例はすべての小課題の制約を満たす．

Notes

JOI 2023 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source