{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"您的公司提供可以用于在体育赛事和音乐会后清理田野上垃圾的机器人。在机器人被分配到任务之前,会对田野进行航拍并标记网格。网格中每个包含垃圾的位置都会被标记。所有机器人都从西北角开始移动,最终在东南角结束。机器人只能向东或向南移动。当机器人进入一个包含垃圾的单元格时,会先清理垃圾然后继续前进。一旦机器人到达东南角的目的地,就不能重新定位或重复使用。由于您的费用与用于特定任务的机器人数量成正比,您希望找到能够清理给定田野的最少机器人数量。例如,考虑图1中显示的田野地图,其中行和列如所示编号,垃圾位置用 \u0027G\u0027 标记。在此方案中,所有机器人将从位置 1,1 开始,结束于位置 6,7。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/6e79adf9610e06d5554dc8e0cba59826?v\u003d1715775556\"\u003e\r\u003cbr\u003e图1 - 田野地图\u003c/center\u003e\r\u003cbr\u003e下面的图2显示了两种可能的解决方案,第二种更可取,因为使用了两台机器人而不是三台。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/9afdaf145038f017702bbc724d5e7466?v\u003d1715775556\"\u003e\r\u003cbr\u003e图2 - 两种可能的解决方案\u003c/center\u003e\r\u003cbr\u003e您的任务是创建一个程序,确定清理田野上所有垃圾所需的最少机器人数量。"}},{"title":"输入","value":{"format":"HTML","content":"输入包括一个或多个田野地图,后跟一行包含 -1 -1 以表示输入数据的结束。一个田野地图包括一个或多个行,每个行包含一个垃圾位置,然后是一行包含 0 0 以表示地图结束。每个垃圾位置包括两个整数,行和列,用一个空格分隔。行和列的编号如图1所示。垃圾位置将按行优先顺序给出。单个田野地图的行数和列数不会超过24行和24列。下面的示例输入显示了一个包含两个田野地图的输入文件。第一个是图1中的田野地图。"}},{"title":"输出","value":{"format":"HTML","content":"输出将包括每个田野地图的单行,其中包含清理相应田野所需的最少机器人数量。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\r\n1 4\r\n2 4\r\n2 6\r\n4 4\r\n4 7\r\n6 6\r\n0 0\r\n1 1\r\n2 2\r\n4 4\r\n0 0\r\n-1 -1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}