一个立体的分割蛋糕的算法问题,请问如何利用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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
几何对称和最小剪裁次数的算法问题,如何利用C语言计算的
0
数据结构对于棋盘的一个分割子的算法的问题,运用C语言技术的编程实现
0
分项的条件的判断的一个算法的问题,如何利用C语言的方式解决的
0
先排序再寻找的算法问题是如何利用C语言设计语言的方式实现的
0
寻找存在的区间的整数的算法问题,怎么利用C语言程序的算法来实现的
0
英文单词的编码的算法问题,如何利用C语言程序编写来解决?
0
切蛋糕的一个算法问题,计算每块边长,运用C语言程序的编写的技术
0
一个矩形构成的矩阵的算法问题,如何利用C程序的设计的语言的方式实现呢
0
同心圆平分蛋糕的算法问题,如何利用C语言程序的设计来实现这个题目的
0
典型的好汉排名的一个算法的问题,利用C语言的程序的设计如何实现
0
质量分割采用试探的算法,怎么利用C语言的程序的设计的思想来实现的?
0
坐标图形的遮挡判断的一个算法的问题,如何利用C语言的程序编写的方式去实现的?
0
最短的路径的判断的计算的一个算法问题,怎么利用C语言的程序的设计实现的?
0
提取数列中的因子的一个算法问题,怎么利用C语言的程序的计算的方式实现?
0
图上的边的直径的计算的算法问题,怎么利用C语言的程序的代码的计算的方式?
0
一个迷宫的便利的典型的算法问题,怎么利用C语言程序代码思路解题的过程?
1
求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)
0
二进制的数字的一个分组的算法问题,是如何利用C语言程序设计的编程的思想方法来有效实现的
1
Java语言如何实现一个算法
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现