1.2　抄近路

【题目描述】 抄近路（shortline）

琳琳每天要从家走到车站，她家小区到车站的道路被分成许多个正方形的块，共有N×M个。有的方块表示房屋，所以琳琳只能沿着附近的街道行走；有的方块表示公园，那么琳琳就可以直接沿对角线穿过去。

请你帮琳琳计算一下从家到车站的最短距离。

【输入格式】

第一行是N和M（0＜N，M≤1 000）。注意：琳琳家在方块(1,1)的西南角，车站在方块(M,N)的东北角。每个方块的边长为100米。接下来的一行是整数K，表示可以沿对角线穿过的方块数。然后有K行，每行有两个数，表示一个坐标。

【输出格式】

输出最短距离，四舍五入到整数，单位为米。

【输入样例】

3 2

3

1 1

3 2

1 2

【输出样例】

383

【算法分析】

本题可以通过从左到右、从下到上逐格递推的方式推导出结果。

下面进一步分析问题的本质。

如果不能斜穿公园，那么无论怎么走，最短距离都是一样的，所以要找到最短距离，需要尽可能多地斜穿公园。如图1.2所示，在由粗线条连起来的最优路径中，经过的公园按横坐标递增和纵坐标递增考虑，这显然是一个最长不下降子序列问题。

图1.2