TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1607
  • 题目
  • P1607清洁机器人
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    何老板的公司生产了一种机器人,可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前,给出了一张网格状的地图,每个包含垃圾的格子都被标记上了“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