一个骑士位于位置(a,b),需要拿走位于(c,d)的国王。我怎样才能:
A:可视化游览
B:计算从 (a,b) 到 (c,d) 所需的最小步数
我发现的实现基本上是一个马在棋盘上的一系列移动,这样马只访问每个方格一次,但我想更具体并进入特定位置。
我应该寻找什么样的算法或策略?
我正在考虑使用 python
最佳答案
您可以使用 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 算法。
关于algorithm - 骑士之旅,计算从 A 到 B 的步数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39628430/