最少数目的车
   

　　一个锯齿形棋盘，是一种从左到右的边界象楼梯状的棋盘，如图所示。

　　　　　　　　　　　　　　　

　　如果某个格子的同一行或同一列有一个棋子车，则这个格子被控制。你的任务就是确定出最少的棋子"车"的个数，使得棋盘上的每一个格子被至少一个"车"所控制。在上例中，只要4个"车"放置在图中黑点表示的格子中，就可以完全控制整个棋盘。

　　输入

　　输入文件包含多组测试数据，每一组测试数据包含不多于100对整数，分别表示棋盘上从左上角开始按顺时针方向的各个拐角点的行列坐标。如上例中拐角点分别为v1,v2，…，v12。拐角点的坐标值分别在[1，100]之内。如上例中的v1,v2,v3，三个点的坐标分别为(1,1)，（1,4），（3，4）。每一组测试数据以一对0表示结束（这对0，不作处理），在所有测试数据结束之后也有一对0表示。

　　输出

　　对于每组测试数据输出一行包含一个整数，表示最少的"车"的数目。

　　Sample Input

　　1 1 1 4 3 4 3 6 4 6
　　4 7 8 7 8 6 6 6 6 3
　　4 3 4 1 0 0 1 1 1 3
　　3 3 3 6 5 6 5 2 3 2
　　3 1 0 0 0 0

　　Sample Output

　　4
　　3
　　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有