#2049. 切蛋糕 Cake slicing

切蛋糕 Cake slicing

题目描述

有一个 nn 行 mm 列(1≤n,m≤201 \leq n, m \leq 20)的网络蛋糕上有 kk 个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块,并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃,且切割线总长度最小。求出这个最小总长度。

输入格式

有多组测试数据。

对于每组数据,第一行三个整数 n,m,kn,m,k。

接下来 kk 行每行两个整数 xi,yix_i,y_i 描述第 ii 个樱桃所在位置。

输出格式

对于每组数据,输出一行 Case x: y,其中 xx 表示当前是第 xx 组测试数据,yy 表示答案即切割线最小总长度。

样例

3 4 3
1 2
2 3
3 2
Case 1: 5

题目来源:洛谷 UVA1629