← 返回题目列表

AtCoder · joi2023ho_c

C. 迷宫

中文机器翻译题面 查看原题

配点: 100 点

問題文

喜欢解迷宫的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) 设为白色。

使用印章可能会弄脏您的手,因此您需要尽量减少使用它的次数。给定方块的绘制方式、图章的大小以及起点和目标方块,编写一个程序来找到最少的操作次数,以便有一条从起点到目标仅通过白色方块的路径。


入力

输入是按以下格式从标准输入给出的。

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) 的颜色,. 表示方块的颜色为白色,# 表示该方块的颜色是黑色。

出力

标准输出中显示了确保从起点到目标仅通过白色方块的路径的最少操作数。 1 行。 在


制約

  • 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 是一个整数。

小課題

  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 点)没有额外的限制。 选择

入力例 1

2 4 2
1 1
2 4
.###
###.

出力例 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 满足约束。


入力例 2

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

出力例 2

4

此输入示例满足所有子任务约束。


入力例 3

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

出力例 3

1

此输入示例是一个小作业。 2, 3, 4, 5, 6, 7, 8 满足约束。


入力例 4

1 15 1
1 15
1 1
...............

出力例 4

0

操作 1 可能有一条从起点到目标的路径只经过白色方块,即使您一次都没有经过。

此输入示例满足所有子任务约束。