#2390. 「JOISC 2017 Day 1」开荒者

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOISC 2017 Day1 T1「開拓Cultivation

开荒者要让一片长方形的平原长满草。这个长方形可视为 R C 列的正方形网格,底平行于南北方向,高平行于东西方向。我们用 (1,1) 表示网格的西北角, (R,C) 表示网格的东南角。开始时有且只有 N 个网格内长有野草,其余网格内既没有草也没有草籽。开荒者们可以控制这片平原上的风往东、西、南、北四个方向中的一个方向吹。

每年夏天,草会制造草籽。开荒者们会选定当年夏天的风向。所有草籽会被风扬起,并根据风向移动一格。来年春天,有草籽降落的网格就会有草萌发。假设草不会枯萎。
我们假设不会有草籽从平原外飘进平原内,飘出网格的草籽不会发芽。试求:让这片平原长满草最少需要几年。

输入格式

第一行有两个整数 R, C ,用空格分隔。
第二行有一个整数 N
在接下来的 N 行中,第 i (1\le i\le N) 有两个整数 S_i, E_i ,表示 (S_i, E_i) 长有野草。

输出格式

一个整数,表示在理想方案下,这片平原长满草最少需要的年数。

样例

样例输入 1

3 4
3
1 2
1 4
2 3

样例输出 1

3

样例解释 1

初始状态( 0 表示有草):

  0   0
   0  
    

一种最佳方案是三年的风向分别为西、南、南。表格中展示了每个格子在哪一年开始长草。

1 0 1 0
2 1 0 2
3 2 2 3

样例输入 2

4 4
4
1 1
1 4
4 1
4 4

样例输出 2

4

数据范围与提示

对于所有数据, 1\le N\le 300, 1\le R, C\le 10^9, 1\le S_i \le R, 1\le E_i\le C, (S_i, E_i)≠(S_j, E_j)(1\le i<j\le N)

Subtask # 分值 R,C N
1 5 R,C\le 4 N\le 16
2 10 R,C\le 40 -
3 15 R\le 40
4 30 - N\le 25
5 20 N\le 100
6 -