Description

小明爱玩跑跑卡丁车游戏，最爱玩的图起始点在一个N*M矩阵的左下角map[1，1]，终点在矩阵的右上角map[n,m]。

游戏里有很多捷径是可以直接穿越的，比如下图中，map[1,1]可以直接到达map[2,2]。map[3,2]可以直接到达map[4,3]。map[1,2]可以直接到达map[2,3]。

已知每一个方格的边长都是100米，小明想找到最近的一条路，希望你帮他算出从起点到终点的最短距离。

Input Format

本题有多组数据。以EOF为输入结束的标志。

每组测试数据的首行为n,m(1 ≤ n,m ≤ 1000000), 第2行为k（1 ≤ k ≤ 1000）表示有多少个特殊的边。

后面k行每行有两个数 i , j ，表示map[i,j]是可以直接穿越的。

Output Format

对于每组数据，输出[1，1]-->[n,m]的最短路径的长度，四舍五入保留到整数即可，每组输出占一行。

3 2
3
1 1
3 2
1 2​

383​

Source

基础百练 动态规划