图2.2
输入：
输入的第一行输入一个整数t，表示测试用例的个数；输入的第二行输入的是第一个测试用例的数据，要输入两个整数，分别是n和k,n表示墙的面数，k表示穿墙者可以通过的墙的最大面数；在上一行后，给出n行，每行包含两个（x,y）对，表示一面墙的两个端点坐标。如上所示的测试用例与图2.1相对应。
输出：
每个测试用例一行，给出一个整数，表示最少拆除墙的面数，使得穿墙者能从上方任意一列开始穿越。
2.有3个测试用例的运行结果如图2.3所示：
图2.3
说明：当输入的测试用例的个数大于等于2时，要先输入完第一个测试用例的数据，输出结果后，再一次输入后面的测试用例的数据。
三．贪心算法特点及存在的问题
3.1 贪心算法特点
从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，不依赖于未做出的选择。贪心算法的最大特点就是快，通常是线性到二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。
3.2 贪心算法存在的问题
(1)不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑。
(2)贪心算法只能用来求某些最大或最小解的问题。从前面的讨论中，找零
钱问题要求得到最小数量采用贪心算法是可行的，但是在另外一个求解权值最小路径时采用贪心算法得到的结果并不是最佳。
(3)贪心算法只能确定某些问题的可行性范围。
四．结束语
贪心算法是计算机算法策略中常用的一个，往往在需要解决一些最优性问题时，都可以应用贪心算法。贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。贪心算法在科学计算和工程中的应用也越来越广泛，例如用贪心算法进行三角剖分的指纹匹配方法、贪心算法在排课系统中的应用、贪心聚类算法及其在遥感图像分类和压缩中的应用等等，在未来出现的一些问题中，只要符合贪心算法的贪心策略性质，就可以用贪心算法求解。总之，我们应该不断推广贪心算法的应用，让它能解决更广泛的问题。