确定给定障碍物可以行驶多少点
determine how many points one can travel given obstacles
假设我们有一个带坐标的场地，机器人从(0, 0)开始，可以上下左右移动，但不能沿对角线移动。
对于任何给定位置 (x, y)，机器人可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1)，但不能移动到 (x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1)。
此外，还有一些障碍物的设置方式是坐标数字加起来等于或大于21的位置，例如(45, -94)是障碍点因为4 + 5 + 9 + 4 = 22 >= 21，但是(-112, 223)不是因为1 + 1 + 2 + 2 + 2 + 3 = 11 < 21.
机器人不能踏入或穿过障碍物。它必须绕着它移动。
要确定机器人可以到达的位置数，首先想到的是使用广度优先搜索进行穷举搜索。
- 这是唯一的方法吗？
- 有更快的方法吗？
- 障碍物的知识如何解决？
如果 x 或 y = +/- 399，则点是障碍物，因此存在从 (-399,-399) 到 (399,399) 的障碍点的完整矩形。
由于您无法到达该矩形之外的任何东西，因此可到达的点少于 640000 个，简单的 BFS 可能是一个合理的解决方案。
假设我们有一个带坐标的场地，机器人从(0, 0)开始，可以上下左右移动，但不能沿对角线移动。
对于任何给定位置 (x, y)，机器人可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1)，但不能移动到 (x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1)。
此外，还有一些障碍物的设置方式是坐标数字加起来等于或大于21的位置，例如(45, -94)是障碍点因为4 + 5 + 9 + 4 = 22 >= 21，但是(-112, 223)不是因为1 + 1 + 2 + 2 + 2 + 3 = 11 < 21.
机器人不能踏入或穿过障碍物。它必须绕着它移动。
要确定机器人可以到达的位置数，首先想到的是使用广度优先搜索进行穷举搜索。
- 这是唯一的方法吗？
- 有更快的方法吗？
- 障碍物的知识如何解决？
如果 x 或 y = +/- 399，则点是障碍物，因此存在从 (-399,-399) 到 (399,399) 的障碍点的完整矩形。
由于您无法到达该矩形之外的任何东西，因此可到达的点少于 640000 个，简单的 BFS 可能是一个合理的解决方案。