编程介的小学生
2019-03-26 16:29切蛋糕的一个算法问题,计算每块边长,运用C语言程序的编写的技术
Problem Description
A rectangular cake with a grid of m*n unit squares on its top needs to be sliced into pieces. Several cherries are scattered on the top of the cake with at most one cherry on a unit square. The slicing should follow the rules below:
1. each piece is rectangular or square;
2. each cutting edge is straight and along a grid line;
3. each piece has only one cherry on it;
4. each cut must split the cake you currently cut two separate parts
For example, assume that the cake has a grid of 3*4 unit squares on its top, and there are three cherries on the top, as shown in the figure below.
One allowable slicing is as follows.
For this way of slicing , the total length of the cutting edges is 2+4=6.
Another way of slicing is
In this case, the total length of the cutting edges is 3+2=5.
Give the shape of the cake and the scatter of the cherries , you are supposed to find
out the least total length of the cutting edges.
Input
The input file contains multiple test cases. For each test case:
The first line contains three integers , n, m and k (1≤n, m≤20), where n*m is the size of the unit square with a cherry on it . The two integers show respectively the row number and the column number of the unit square in the grid .
All integers in each line should be separated by blanks.
Output
Output an integer indicating the least total length of the cutting edges.
Sample Input
3 4 3
1 2
2 3
3 2
Sample Output
Case 1: 5
- 点赞
- 回答
- 收藏
- 复制链接分享
0条回答
为你推荐
- 利用C语言的程序设计的技术,计算这个图中的最长最短路径的算法怎么实现
- r语言
- Golang
- erlang
- 1个回答
- C语言数据结构的模拟银行存钱取钱的算法,采用C语言程序的编写
- r语言
- Golang
- erlang
- 1个回答
- 一个关于C语言向量计算方面数据结构的算法的问题,采用C语言
- r语言
- Golang
- erlang
- 1个回答
- 一个有关数据库遇到的算法障碍的问题怎么解决?C语言
- 数据库
- lines
- as
- c语言
- 1个回答
- 一个有关排序算法的编程方面的难题,C语言解决
- lines
- c语言
- 编程
- 1个回答