TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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