레이팅 미적용迷路を解くのが好きなK 理事長は,迷路になりそうなマス目を見つけた.マス目は縦R 行,横C 列の
長方形の形をしており,各マスは白または黒で塗られている.上からi 行目(\(1 \le i \le R\)),左からj 列目
(\(1 \le j \le C\)) のマスをマス(i, j) と呼ぶことにする.
K 理事長は,マス目の白いマスは通れるマス,黒いマスは通れないマスとして,迷路を解くことにした.
具体的には,以下のようにして迷路を解く.
1. 白いマスの中からスタートのマス(S r, S c) とゴールのマス(Gr,Gc) を選ぶ.
2. 上下左右に隣接する白いマスに移動することを繰り返して,スタートのマスからゴールのマスへ移動
する経路を見つける.
K 理事長はスタートのマスとゴールのマスを決めたが,マス目の色の塗られ方によっては,白いマスのみ
を通ってスタートからゴールへ移動する経路が存在しない場合があることに気がついた.そこで,K 理事
長の持っている\(N \times N\) マスの大きさのハンコを用いて以下の操作を繰り返すことで,スタートからゴール
へ移動する経路が存在するようにしたい.
操作マス目から\(N \times N\) マスの正方形の領域を選び,この領域に含まれるマスをすべて白にする.より
厳密には,1 ≦a ≦R −N + 1,1 ≦b ≦C −N + 1 を満たす整数a, b を選び,a ≦i ≦a + N −1,
b ≦j ≦b + N −1 を満たすすべての整数の組(i, j) に対して,マス(i, j) を白にする.
ハンコを使うと手が汚れる可能性があるため,操作回数はできるだけ少なくしたい.マス目の塗られ方と
ハンコの大きさ,スタートのマスとゴールのマスが与えられたとき,白いマスのみを通ってスタートから
ゴールへ移動する経路が存在するようにするための,操作回数の最小値を求めるプログラムを作成せよ.
第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)
• \(1 \le N \le R \le C\).
• R × C ≦6 000 000.
• 1 ≦S r ≦R.
• 1 ≦S c ≦C.
• \(1 \le Gr \le R\).
• \(1 \le Gc \le C\).
• (S r, S c) , (Gr,Gc).
• Ai (\(1 \le i \le R\)) は. または# からなる長さC の文字列である.
• マス(S r, S c) の色は白である.
• マス(Gr,Gc) の色は白である.
• R,C, N, S r, S c,Gr,Gc は整数である.
第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)
- (8 点) N = 1,R × C ≦1 500 000.
- (19 点) R × C ≦1 000.
- (16 点) 答えは10 以下である,R × C ≦1 500 000.
- (19 点) R × C ≦60 000.
- (5 点) R × C ≦150 000.
- (19 点) R × C ≦1 500 000.
- (8 点) R × C ≦3 000 000.
- (6 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
R C N
S r S c
Gr Gc
A1
A2
...
AR
Ai (\(1 \le i \le R\)) は. または# からなる長さC の文字列である.Ai のj 文字目(\(1 \le j \le C\)) はマス(i, j) の色
を表し,. はそのマスの色が白であることを,# はそのマスの色が黒であることを表す.
標準出力に,白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための操作
回数の最小値を1 行で出力せよ.
2 4 2
1 1
2 4
.###
###.
1
6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###
4
6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.
1
1 15 1
1 15
1 1
...............
0