Okabe and City

题意翻译

Okabe喜欢沿着有路灯的小路穿行城市。但是如果沿途的路灯没有点亮，在一片漆黑中，他就会被他那些跑得超级快的小伙伴抛弃。 Okabe居住的苟城可以用一个二维网格表示。行从上到下编为1~N，列从左到右编为1~N。有K盏路灯是亮着的。初始时左上角的路灯已点亮。 Okabe开始了他的旅程。他从左上角出发，目的地是右下角。.当然，Okabe只会经过点亮的灯，而且只能向相邻的上、下、左、右单元走。然而，Okabe也可以支出1s的寿命来暂时点亮某一行或某一列的灯，从而通过一些最初没有点亮的区域。 值得注意的是，Okabe在同一时间内只能点亮某一行或某一列的路灯，且在每次点亮新的行列时都必须重新-1s。要更改临时点亮的行和列时，他必须站在一开始就亮着的地方。而当他更改时，被点亮的一整行或一整列灯会同时熄灭。 由于Okabe的寿命是有限的，请帮助Okabe找出最少需要支出多少寿命来完成这次旅行。 输入 输入的第一行包括三个整数n、m、k，中间用空格隔开。(2 ≤ n, m, k ≤ 104). 接下来的k行，每行有两个整数 ri 和 ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) ，表示初始时已经点亮的灯的行和列。 输入保证每个被点亮的灯的坐标不重合，且左上角的灯一定是亮的。 输出 输出Okabe到达目的地需要支出的最少寿命。如果不可能到达，输出-1。

题目描述

Okabe likes to be able to walk through his city on a path lit by street lamps. That way, he doesn't get beaten up by schoolchildren. Okabe's city is represented by a 2D grid of cells. Rows are numbered from $ 1 $ to $ n $ from top to bottom, and columns are numbered $ 1 $ to $ m $ from left to right. Exactly $ k $ cells in the city are lit by a street lamp. It's guaranteed that the top-left cell is lit. Okabe starts his walk from the top-left cell, and wants to reach the bottom-right cell. Of course, Okabe will only walk on lit cells, and he can only move to adjacent cells in the up, down, left, and right directions. However, Okabe can also temporarily light all the cells in any single row or column at a time if he pays $ 1 $ coin, allowing him to walk through some cells not lit initially. Note that Okabe can only light a single row or column at a time, and has to pay a coin every time he lights a new row or column. To change the row or column that is temporarily lit, he must stand at a cell that is lit initially. Also, once he removes his temporary light from a row or column, all cells in that row/column not initially lit are now not lit. Help Okabe find the minimum number of coins he needs to pay to complete his walk!

输入输出格式

输入格式

The first line of input contains three space-separated integers $ n $ , $ m $ , and $ k $ ( $ 2<=n,m,k<=10^{4} $ ). Each of the next $ k $ lines contains two space-separated integers $ r_{i} $ and $ c_{i} $ ( $ 1<=r_{i}<=n $ , $ 1<=c_{i}<=m $ ) — the row and the column of the $ i $ -th lit cell. It is guaranteed that all $ k $ lit cells are distinct. It is guaranteed that the top-left cell is lit.

输出格式

Print the minimum number of coins Okabe needs to pay to complete his walk, or -1 if it's not possible.

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

5 5 4
1 1
2 1
3 1
3 2

输出样例 #2

-1

输入样例 #3

2 2 4
1 1
1 2
2 1
2 2

输出样例 #3

0

输入样例 #4

5 5 4
1 1
2 2
3 3
4 4

输出样例 #4

3

说明

In the first sample test, Okabe can take the path , paying only when moving to $ (2,3) $ and $ (4,4) $ . In the fourth sample, Okabe can take the path , paying when moving to $ (1,2) $ , $ (3,4) $ , and $ (5,4) $ .

题意翻译

Okabe喜欢沿着有路灯的小路穿行城市。但是如果沿途的路灯没有点亮，在一片漆黑中，他就会被他那些跑得超级快的小伙伴抛弃。 Okabe居住的苟城可以用一个二维网格表示。行从上到下编为1~N，列从左到右编为1~N。有K盏路灯是亮着的。初始时左上角的路灯已点亮。 Okabe开始了他的旅程。他从左上角出发，目的地是右下角。.当然，Okabe只会经过点亮的灯，而且只能向相邻的上、下、左、右单元走。然而，Okabe也可以支出1s的寿命来暂时点亮某一行或某一列的灯，从而通过一些最初没有点亮的区域。 值得注意的是，Okabe在同一时间内只能点亮某一行或某一列的路灯，且在每次点亮新的行列时都必须重新-1s。要更改临时点亮的行和列时，他必须站在一开始就亮着的地方。而当他更改时，被点亮的一整行或一整列灯会同时熄灭。 由于Okabe的寿命是有限的，请帮助Okabe找出最少需要支出多少寿命来完成这次旅行。 输入 输入的第一行包括三个整数n、m、k，中间用空格隔开。(2 ≤ n, m, k ≤ 104). 接下来的k行，每行有两个整数 ri 和 ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) ，表示初始时已经点亮的灯的行和列。 输入保证每个被点亮的灯的坐标不重合，且左上角的灯一定是亮的。 输出 输出Okabe到达目的地需要支出的最少寿命。如果不可能到达，输出-1。