骑士的最短路径(BFS)
Shortest path for the knight (BFS)
请帮助我理解我的代码做错了什么。我正在尝试使用 BFS 获得最短路径来解决问题,但它要么给我 -1 要么 2。它应该给我 6 作为答案。我究竟做错了什么?这是问题所在:
给定一个棋盘,找出一个骑士从给定源到达给定目的地所走的最短距离(最少步数)。
例如,N = 8(8 x 8 板),来源 = (7, 0) 目的地 = (0, 7)
所需的最少步数为 6
我的代码如下:
class Point {
int x, y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
class knightShortestPath {
int N = 8;
public static boolean visited[][];
public boolean isPositionValid(int x, int y){
if( x < 0 || y < 0 || x > this.N || y > this.N){
return false;
}
return true;
}
public void createChessBoard(int N) {
this.N = N;
visited = new boolean[this.N][this.N];
for (int i = 0; i < this.N; i++) {
for (int j = 0; j < this.N; j++) {
visited[i][j] = false;
}
}
}
public int BFS(Point source, Point destination) {
int row[] = {2, 2, -2, -2, 1, 1, -1, -1};
int col[] = {1, -1, 1, -1, 2, -2, 2, -2};
Queue<Point> queue = new LinkedList<>();
queue.offer(source);
visited[source.x][source.y] = true;
int minimumNumSteps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Point pt = queue.poll();
if (pt.x == destination.x && pt.y == destination.y) {
return minimumNumSteps;
}
for (int j = 0; j < size; j++) {
Point next = new Point(pt.x + row[i], pt.y + col[j]);
if (isPositionValid(pt.x + row[i], pt.y + col[j]) && !visited[i][j]) {
visited[i][j] = true;
queue.offer(next);
}
}
}
minimumNumSteps++;
}
return minimumNumSteps;
}
public static void main(String[] args) {
knightShortestPath position = new knightShortestPath();
position.createChessBoard(8);
Point src = new Point(0,7);
Point dest = new Point(7,0);
System.out.println("The minimum number of steps are: " + position.BFS(src, dest)); //answer is 6
}
}
第一件事:我不知道你怎么会得到一个负值。用 0 初始化后,您永远不会减少 minimumNumSteps
。可能是溢出?我觉得很奇怪..
除此之外,我还看到两个问题:
- 两个for循环不正确。您当前迭代
queue.size()
。您要做的是遍历当前节点的所有子节点。
- 轮询 for 循环之外的当前点。
所以:
while(!queue.isEmpty()) {
Point pt = queue.poll();
// check if it's target
// ...
for (int i = 0; i < row.length; i++) {
// ...
for (int j = 0; j < col.length; j++) {
// ...
}
}
}
另注:当队列为空且未达到目标时,无解。目前,您正在返回一些可能被错误解释的值。
请帮助我理解我的代码做错了什么。我正在尝试使用 BFS 获得最短路径来解决问题,但它要么给我 -1 要么 2。它应该给我 6 作为答案。我究竟做错了什么?这是问题所在:
给定一个棋盘,找出一个骑士从给定源到达给定目的地所走的最短距离(最少步数)。
例如,N = 8(8 x 8 板),来源 = (7, 0) 目的地 = (0, 7)
所需的最少步数为 6
我的代码如下:
class Point {
int x, y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
class knightShortestPath {
int N = 8;
public static boolean visited[][];
public boolean isPositionValid(int x, int y){
if( x < 0 || y < 0 || x > this.N || y > this.N){
return false;
}
return true;
}
public void createChessBoard(int N) {
this.N = N;
visited = new boolean[this.N][this.N];
for (int i = 0; i < this.N; i++) {
for (int j = 0; j < this.N; j++) {
visited[i][j] = false;
}
}
}
public int BFS(Point source, Point destination) {
int row[] = {2, 2, -2, -2, 1, 1, -1, -1};
int col[] = {1, -1, 1, -1, 2, -2, 2, -2};
Queue<Point> queue = new LinkedList<>();
queue.offer(source);
visited[source.x][source.y] = true;
int minimumNumSteps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Point pt = queue.poll();
if (pt.x == destination.x && pt.y == destination.y) {
return minimumNumSteps;
}
for (int j = 0; j < size; j++) {
Point next = new Point(pt.x + row[i], pt.y + col[j]);
if (isPositionValid(pt.x + row[i], pt.y + col[j]) && !visited[i][j]) {
visited[i][j] = true;
queue.offer(next);
}
}
}
minimumNumSteps++;
}
return minimumNumSteps;
}
public static void main(String[] args) {
knightShortestPath position = new knightShortestPath();
position.createChessBoard(8);
Point src = new Point(0,7);
Point dest = new Point(7,0);
System.out.println("The minimum number of steps are: " + position.BFS(src, dest)); //answer is 6
}
}
第一件事:我不知道你怎么会得到一个负值。用 0 初始化后,您永远不会减少 minimumNumSteps
。可能是溢出?我觉得很奇怪..
除此之外,我还看到两个问题:
- 两个for循环不正确。您当前迭代
queue.size()
。您要做的是遍历当前节点的所有子节点。 - 轮询 for 循环之外的当前点。
所以:
while(!queue.isEmpty()) {
Point pt = queue.poll();
// check if it's target
// ...
for (int i = 0; i < row.length; i++) {
// ...
for (int j = 0; j < col.length; j++) {
// ...
}
}
}
另注:当队列为空且未达到目标时,无解。目前,您正在返回一些可能被错误解释的值。