切蛋糕的一个算法问题,计算每块边长,运用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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

4
C++语言编程 运用贪心算法的方法
1
一个有关于切分蛋糕的算法问题,请问怎么用C语言实现呢?
2
一个c语言的算法循环问题
1
采用算法计算一个几何问题,计算围栏的长度怎么用C语言程序的实现的方式
0
树状节点的编号的一个算法的问题,看下怎么使用C语言编写程序来计算
0
查找最近的车站的一个算法问题,采用邻接矩阵的方式的表述,怎么计算的,运用C语言的相关知识
0
数组在图上的移动的一个算法的问题,要综合运用C语言知识的程序的编写
0
一个立体的分割蛋糕的算法问题,请问如何利用C语言的形式解决
0
序列三元组的计算的算法问题运用的C语言的编程技术如何结局
0
CRASH X算法的计算的问题,如何运用C语言解决这个数据结构
0
一个序列求极值的一个算法的问题,要运用C语言的办法如何才能解决呢
0
数据结构对于棋盘的一个分割子的算法的问题,运用C语言技术的编程实现
0
路径带权边长的计算算法问题,利用C语言编程如何解答呢
0
PBD最小费用算法问题的实现,怎么运用C语言编程来实现这个算法
0
平分蛋糕的算法的问题的求解过程,运用C编程的语言的技术怎么实现的呢
1
三角形各个边长的组合的判断的算法问题,如何运用C程序设计技术来实现
0
广度优先遍历的路径搜索算法问题怎么解决?运用C语言的程序编写方式
0
菲波那契数列(Fibonacci numbers)的一个算法问题,运用C语言实现的形式和做法
0
切分巧克力的算法的一个问题,怎么利用C语言的程序设计的办法?
0
高阶图形的算法问题,图像的匹配数运用C语言程序算法实现怎么实现