0

骑士位于 (a,b) 位置，需要夺取位于 (c,d) 的国王。我怎样才能：

A：可视化游览

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

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

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

我正在考虑使用python

4

2 回答 2

1

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

假设 NXM 棋盘，Point 代表棋盘上的每个块，并在其上应用 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 算法。

于 2016-09-22T00:35:50.447 回答
0

找到骑士巡回问题的准确解决方案的最佳方法是使用回溯算法。查看您可以选择的所有可能步骤（a，b）选择第一个并继续前进，直到找到死胡同。

如果出现死胡同，请退后一步并探索其他选择。

这是DFS（深度优先搜索）的一个例子

于 2016-09-22T05:55:45.643 回答