首页 > 代码库 > Codeforces Round #420 D题翻译(17.6.25)

Codeforces Round #420 D题翻译(17.6.25)

D. Okabe and City

Okabe和苟城

时间限制:4秒

空间限制:256M

输入:标准输入

输出:标准输出

Okabe喜欢沿着有路灯的小路穿行城市。但是如果沿途的路灯没有点亮,在一片漆黑中,他就会被他那些跑得超级快的小伙伴抛弃。

Okabe居住的苟城可以用一个二维网格表示。行从上到下编为1~N,列从左到右编为1~N。有K盏路灯是亮着的。初始时左上角的路灯已点亮。

Okabe开始了他的旅程。他从左上角出发,目的地是右下角。.当然,Okabe只会经过点亮的灯,而且只能向相邻的上、下、左、右单元走。然而,Okabe也可以支出1s的寿命来暂时点亮某一行或某一列的灯,从而通过一些最初没有点亮的区域。

值得注意的是,Okabe在同一时间内只能点亮某一行或某一列的路灯,且在每次点亮新的行列时都必须重新-1s。要更改临时点亮的行和列时,他必须站在一开始就亮着的地方。而当他更改时,被点亮的一整行或一整列灯会同时熄灭。

由于Okabe的寿命是有限的,请帮助Okabe找出最少需要支出多少寿命来完成这次旅行。

输入

输入的第一行包括三个整数nmk,中间用空格隔开。(2 ≤ n, m, k ≤ 104).

接下来的k行,每行有两个整数 ri  ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m,表示初始时已经点亮的灯的行和列。

输入保证每个被点亮的灯的坐标不重合,且左上角的灯一定是亮的。

 

输出

输出Okabe到达目的地需要支出的最少寿命。如果不可能到达,输出-1

样例输

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

样例输出

2

样例输入

5 5 4
1 1
2 1
3 1
3 2

样例输出

-1

样例输入

2 2 4
1 1
1 2
2 1
2 2

样例输出

0

样例输入

5 5 4
1 1
2 2
3 3
4 4

样例输出

3

注释

在第一个样例中,Okabe可以通过以下路线: , (2, 3)  (4, 4)两处-1s,到达目的地.

在第四个样例中,Okabe可以通过以下路线: ,(1, 2), (3, 4),  (5, 4)三处-1s,到达目的地.

Codeforces Round #420 D题翻译(17.6.25)