找到访问网格上所有非阻塞方块的最短路径

Question

假设你有一个这样的网格(随机制作):

现在让我们假设你有一辆汽车从其中一个盒子里随机开始,那么通过每个白盒子的最短路径是什么？您可以根据需要多次访问每个白盒,也不能跳过黑盒子.黑匣子就像墙壁.简单来说,您只能从白框移动到白盒.

您可以向任何方向移动,甚至是对角移动.

两个子问题:

1. 假设您在移动之前知道所有黑匣子的位置.
2. 假设您在与其相邻的白色框中时只知道黑匣子的位置.

Answer 1

尝试将其构建为图表（其中每个节点最多有 8 个其他节点）并将其视为http://en.wikipedia.org/wiki/Travelling_salesman_problem