← 返回题目列表

AtCoder · joigsp2025_f

F. 日本崛起

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

配点: 100 点

日本列岛是一个构造运动活跃的群岛。 日本列岛所在海域有南北。 H 行,東西 W 它由列网格表示。 从北方 r 行,从西边 c 列目 (1 \leqq r \leqq H,1 \leqq c \leqq W) 它被称为 (r,c) 。 每个正方形都是 陸 或 至少 海 。 最初存在于海洋中的陆地只是 N 这是一个正方形,其他的正方形都是海。 最初,这些土地的位置是 (R_1, C_1), (R_2, C_2), \dots, (R_N, C_N) 。

日本列岛每天中午都会发生地壳运动。 t 日目 (t \geqq 1) 中午发生的地壳运动表示如下。

  • 1 \leqq r \leqq H-1,1 \leqq c \leqq W 出 t 当天早上的弥撒 (r, c) 是陆地上的一个正方形。 所有这些都使得 (r+1, c) 是海洋 关于 (r, c) ,质量 (r+1, c) 成为一片新土地。

如果仅通过追踪北、南、东、西彼此相邻的陆地就可以从任何陆地到达任何陆地,则日本列岛被定义为连通的。 随着地壳变形的进展,日本列岛可能会变得相连。

给定一开始的海洋面积信息,编写一个程序,判断日本列岛是否会因为反复地壳变形而连接起来,如果是的话,判断地壳变形会发生多少次才会连接起来。


入力

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

H W N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

出力

如果要连接日本列岛,标准输出将指示需要多少次地壳运动才能连接。 输出为 1 行。 但是,如果在开头连接 输出 0 。 还有,如果将来日本列岛不连通的话, -1 。

制約

  • 1 \leqq H \leqq 200\,000.
  • 1 \leqq W \leqq 200\,000.
  • 2 \leqq N \leqq \min(H \times W,\ 200\,000).
  • 1 \leqq R_i \leqq H (1 \leqq i \leqq N).
  • 1 \leqq C_i \leqq W (1 \leqq i \leqq N).
  • (R_i, C_i) \neq (R_j, C_j) (1 \leqq i < j \leqq N).
  • 所有输入值都是整数。

小課題

  1. (5 点) W = 1.
  2. (9 点) N = 2.
  3. (8 点) H \leqq 500,W \leqq 500,N \leqq 500.
  4. (28 点) N \leqq 2\,000.
  5. (13 点) H \times W \leqq 200\,000.
  6. (13 点) H \times N \leqq 200\,000.
  7. (24 点)没有额外的限制。

入力例 1

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

出力例 1

2

下图是一开始海域的情况。实心方块代表陆地,空白方块代表海洋。

33c09866b226eb567a7d94bd83c55c3e.png

1 第二次地壳变形创造了新的陆地。 (2, 1), (2, 3), (4, 2), (4, 3) 可以得到第 4 。 1 第二次地壳变形后,质量 来自 (1, 1) 到 (4, 4) 日本列岛并不相连,因为仅追踪北、南、东、西相邻的陆地是无法到达的。 下图是 1 这是第二次地壳运动后不久海洋中的情况。阴影方块现在将变成陆地,其他方块将保持不变。

60e4f4b495347e769f52c974bcfd60c2.png

2 第二次地壳变形创造了新的陆地。 (3, 1) 可以得到第 1 。 2 第一次访问后立即海域的情况如下图所示。

ccb260441c5aaba18d776ed62984d820.png

2 由于日本列岛在第二次地壳运动中首次相连,2 。 你只需要砍掉

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


入力例 2

3 3 2
1 1
3 3

出力例 2

-1

由于日本列岛永远不会连接,-1 。 你只需要砍掉

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


入力例 3

2 2 2
1 1
1 2

出力例 3

0

日本列岛甚至在地壳变形发生之前就已经相连,因此0 。 你只需要砍掉

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