P1607清洁机器人 | |
|
问题描述
何老板的公司生产了一种机器人,可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前,给出了一张网格状的地图,每个包含垃圾的格子都被标记上了“G”。所有的机器人一开始都位于西北方的那一角,在工作结束时所有的机器人都会走到东南方的那一角。每个机器人只能往东和往南两个方向行走。一走到有垃圾的格子,机器人就会把垃圾清理掉。一旦机器人走到了东南方那一个角,它就会自动切断电源,不能再次工作。
你的任务是计算出最少需要多少个机器人,就能清理完所有的垃圾。
例如下图:所有的机器人一开始在(1,1)位置,结束时在(6,7)位置
下图展示了两种可能的方案,其中第二种方案更好,因为它只用了两个机器人。
输入格式
由一行或多行构成,每行两个空格间隔的整数,表示一个包含垃圾的格子坐标
输入由0 0 作为结束。
注:每组测试数据的格子坐标是按行由小到大的顺序给出。
地图的行数和列数都不超过24
输出格式
若干行,每行一个整数,表示对应测试数据的结果。
样例输入
1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
样例输出
2
提示
何某翻译
来源 Mid-Central USA 2003 或参阅poj1548