logo AlgoBeat OnlineJudge
登录 注册

#213826. [JOIGST 2025] 日本浮现 / Japan Emerges

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

日本列岛的地壳运动十分激烈。

日本列岛的水域可以视为一个在南北方向上有 行、在东西方向上有 列的网格,从北到南第 行、从西到东第 列记为

初始时有恰好 个格子是陆地,其他格子均为海洋。这 块陆地分别位于格子

日本列岛每天中午都会发生地壳运动。第 日中午的地壳运动可以描述为如下的过程:

  • 若一个格子 满足 在早上(即地壳运动发生之前)为陆地、 在早上为海洋,那么在地壳运动发生之后, 也将成为陆地。

如果从任何一个为陆地的格子出发,都能通过“反复移动到东、西、南、北相邻的陆地格子”到达任何一个其他的为陆地的格子,那么称日本列岛是“连通的”。随着不断的地壳运动,日本列岛可能会在某个时候变成连通的。

判断日本列岛是否会通过若干次地壳运动变为连通的。如果可以,试求出至少需要经过几天才可以变为连通的。

输入格式

第一行输入三个整数

接下来 行,第 行输入两个整数

输出格式

输出一行一个整数,表示日本列岛至少需要几天才能变为连通的。如果日本列岛一开始就是连通的,输出 0;如果不可能通过地壳运动变为连通的,输出 -1

样例

样例输入 1

4 4 5
1 1
1 3
3 2
3 3
4 4

样例输出 1

2

样例输入 2

3 3 2
1 1
3 3

样例输出 2

-1

样例输入 3

2 2 2
1 1
1 2

样例输出 3

0

数据范围与提示

【样例解释 #1】

下图展示了初始时日本列岛的形态(深绿色为陆地,白色为海洋):

天之后, 形成新的陆地。此时日本列岛并不连通( 无法通过反复向四个方向移动到达 )。下图展示了第 天之后日本列岛的形态(深绿色为初始时的陆地,浅绿色为新形成的陆地,白色为海洋):

天之后, 形成新的陆地。此时日本列岛连通了。下图展示了第 天之后日本列岛的形态:

日本列岛在 次地壳运动后变为连通的。

该样例满足子任务 的限制。

【样例解释 #2】

日本列岛无法通过地壳运动变为连通的。

该样例满足子任务 的限制。

【样例解释 #3】

日本列岛在所有地壳运动之前就是连通的。

该样例满足子任务 的限制。

【数据范围】

【子任务】

  1. 分)
  2. 分)
  3. 分)
  4. 分)
  5. 分)
  6. 分)
  7. 分)无附加限制。