algorithm - 骑士之旅，计算从 A 到 B 的步数

Question

一个骑士位于位置(a,b)，需要拿走位于(c,d)的国王。我怎样才能:

A:可视化游览

B:计算从 (a,b) 到 (c,d) 所需的最小步数

我发现的实现基本上是一个马在棋盘上的一系列移动，这样马只访问每个方格一次，但我想更具体并进入特定位置。

我应该寻找什么样的算法或策略？

我正在考虑使用 python

Answer 1

您可以使用 BFS 算法来实现上述目标。只需缓存访问过的位置，这样您就不会多次访问一个位置。现在，每当您访问目的地时，每次完整迭代所采取的步数最少，您正在探索的分离度仅为 1。

假设 N X M 棋盘，Point 代表棋盘上的每个 block 并对其应用 BFS。

class Point{
        int x;
        int y;
        int dist;
}

public int knight(int N, int M, int x1, int y1, int x2, int y2) {
           Point source = new Point(x1, y1);
           Point destination = new Point(x2, y2);

           Queue<Point> q = new LinkedList<>();
           q.add(source);
           Set<Point> hset = new HashSet<>();
           hset.add(source);
           int[][] dir = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};
           while(!q.isEmpty()){
               Point p = q.poll();

               if(p.equals(destination)){
                   return p.dist;
               }

               for(int[] d : dir){

                   int row = p.x + d[0];
                   int col = p.y + d[1];
                   Point temp = new Point(row, col);
                   if(row <= 0 || col <= 0 || row > N || col > M || hset.contains(temp)){
                       continue;
                   }
                   temp.dist = p.dist + 1;

                   q.add(temp);
                   hset.add(temp);

               }

           }

           return -1;   //unreachable point from source position
}

可视化一个游览就简单多了，用ArrayList等来存储遍历的路径就可以了。另一种方法可能是针对上述问题使用 Dijkstra 算法。