TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1607
  • Problem
  • P1607清洁机器人
    Limits : Time Limit : 1000 MS   Memory Limit : 65536 KB
    Description

    何老板的公司生产了一种机器人,可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前,给出了一张网格状的地图,每个包含垃圾的格子都被标记上了“G”。所有的机器人一开始都位于西北方的那一角,在工作结束时所有的机器人都会走到东南方的那一角。每个机器人只能往东和往南两个方向行走。一走到有垃圾的格子,机器人就会把垃圾清理掉。一旦机器人走到了东南方那一个角,它就会自动切断电源,不能再次工作。

    你的任务是计算出最少需要多少个机器人,就能清理完所有的垃圾。
    例如下图:所有的机器人一开始在(1,1)位置,结束时在(6,7)位置

    下图展示了两种可能的方案,其中第二种方案更好,因为它只用了两个机器人。

    Input Format

    由一行或多行构成,每行两个空格间隔的整数,表示一个包含垃圾的格子坐标
    输入由0 0 作为结束。

    注:每组测试数据的格子坐标是按行由小到大的顺序给出。

    地图的行数和列数都不超过24

    Output Format

    若干行,每行一个整数,表示对应测试数据的结果。

    Sample Input

    1 2
    1 4
    2 4
    2 6
    4 4
    4 7
    6 6
    0 0

    Sample Output

    2

    Hint

    何某翻译


    Source  Mid-Central USA 2003 或参阅poj1548