图以使用我访问过的节点找到到原点的最短路径

Question

给出方向和路线，我想知道最短的路径，最后，仅使用之前访问过的地方回到我的起点（起源）

（（下面图像的示例，N是北，S是南等）

样本输入：NNEEEENWNENNSEEEWWWSWSESWWWNNNNWWWSSSNNNNEE

样本输出：14

image with example, red is shortest path and gives the 14 output

我在Java中工作，想要使用广度优先搜索算法，并且想要使用图形，这是构造此图形并查看此问题的最佳方法？

有人可以帮忙吗？

Answer 1

您可以通过读取输入来生成访问单元的图形，然后从最后一个位置对该图形运行BFS。

要生成图形，您可以执行以下操作：

for each direction :
   create node for the cell if not already existing
   for each adjacent cell, if visited then connect them together