algorithm - 迷宫需要多少变化才能到达目的地？

Question

我遇到了这个面试问题。第一部分如下:

You are given matrix containing letters 'U', 'D', 'L', 'R' and 'X'. 'U' allow you to move up, 'L' allows to move left, etc. 'X' is the destination. Check if it is possible to reach the destination from the top left corner.

这部分使用 DFS 很容易完成。不过，我对第二部分很纠结:

How many edits (e.g. change 'U' -> 'L') you need to make in order to reach X

我假设这可以通过修改后的 BFS 来完成，该 BFS 会计算我们违背指定方向的次数。有人可以给点提示吗？

Answer 1

本质上，您想要计算从左上角到矩阵的每个元素(特别是标记为 X 的元素)的所谓“编辑距离”，通过我的意思是为了能够从左上角到达给定元素，您必须在矩阵中进行的编辑次数。

要做到这一点，您可以首先找到“编辑距离”为零的所有元素，即左上角和从它可以到达的所有元素。 (你提到你可以为此使用深度优先搜索，但它甚至不是真正的“搜索”，因为每个元素都会准确地告诉你哪个元素在它之后。所以从左上角只有一条路径，要么在 X 处结束，以“离开”边缘或进入循环结束。)

然后您可以使用广度优先搜索，从您刚刚找到的元素集开始。对于任何给定的 d，编辑距离 = d + 1 的元素都是:

• 没有编辑距离≤d；
• 以及:
  • 是编辑距离为 d 的元素的邻居
  • 或者可以从这样的邻居联系到

您可以在计算出标记为 X 的正方形的编辑距离后立即停止。

这种方法最多访问每个元素一次，所以如果矩阵有 N 个元素，这种方法需要 O(N) 时间和空间。