OI题库

【题目描述】

作为受雇于一个飞行控制中心的首席程序员，你刚刚接到了一个监控特定区域内飞机活动的任务。

由于这一区域内的一些飞机离控制中心太远，以至于传感器无法将其锁定，因此确定区域内飞行器的实际数目是不可能的。但是，控制中心传感器阵列的扫描结果显示了区域中每个方格状空域内检测到的能量总数，并且通过分析这些数据，你可以得到区域的大致情况。

你决定首先编写一个程序来简化对最小飞机数量的计算。你需要遵守以下规则：

1.传感器阵列没有读数的空域没有飞机。

2.读数是正数的空域有飞机的航迹。在这片空域内，

    a)有一架飞机。

    或b)它恰好是一架飞机的航迹，这架飞机曾经竖直或水平地经过这片空域（注意，飞机无法在半路改变飞行方向）。

3.如果同一行或同一列中一些相邻的空域是一架飞机的航迹，那么每片空域中的能量总数（从上到下或从左到右）必须严格递增或严格递减。

【输入格式】

输入文件包含至多3组数据。

每组数据的第一行是两个正整数N,M(1<=N<=50,1<=M<=9)，即要求监控的区域大小。

接下来的N行，每行包含M个正整数。第i行第j列的数代表传感器阵列在相应空域中检测到的能量总数。保证输入文件的所有数据都在32位带符号整数范围内。

输入结束标志为N=M=0.

【输出格式】

对每组数据，输出一行，其中包含整个区域内飞机数量的最小可能值。具体格式见样例。

【样例输入】

3 3

1 2 3

4 5 6

7 8 9

0 0

【样例输出】

Case 1: 3

【提示】

对于30%的数据,1<=N<=10,1<=M<=5

对于100%的数据，1<=N<=50,1<=M<=9

【来源】

UVa1408 Flight Control