java - 如何实现 BFS(而不是我的解决方案，使用树结构)

Question

我一直在努力寻找以下问题的解决方案“http://wcipeg.com/problems/desc/ccc10j5” '.基本上，您在 2D 网格 (x, y) 上得到一个点。您必须找到从起点到终点的最短路径(也已给出)。

限制:您只能以“L”形旅行(就像国际象棋中的骑士)。

虽然我能够解决它，但人们一直告诉我有更好的方法来解决它，使用树结构(或其他东西)。可以帮助我加快我的解决方案。

这是我的代码。

import java.util.Scanner;

public class oj{     

static int steps = 0;
static int screen[][] = new int[9][9];

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x, y;
        x = scan.nextInt();
        y = scan.nextInt();
        int endx = scan.nextInt();
        int endy = scan.nextInt();

        for(int i = 1; i <= 8; i++)
            for(int j = 1; j <= 8; j++)
                screen[i][j] = 99999;

        doHop(x, y, 0);
        System.out.println(screen[endx][endy]);         
    }
    public static void doHop(int x, int y, int steps){
        if(x > 0 && x <= 8 && y > 0 && y <= 8 && steps < screen[x][y]){
            screen[x][y] = steps;
             doHop (x - 1, y + 2, steps + 1);
             doHop (x - 1, y - 2, steps + 1);
             doHop (x + 1, y + 2, steps + 1);
             doHop (x + 1, y - 2, steps + 1);
             doHop (x - 2, y + 1, steps + 1);
             doHop (x - 2, y - 1, steps + 1);
             doHop (x + 2, y + 1, steps + 1);
             doHop (x + 2, y - 1, steps + 1);
        }
    }
}

提前致谢。

Answer 1

这是图上的最短路径问题，并且由于图未加权 - BFS确实最佳地解决了问题(找到最接近的解决方案)，而您的解决方案是 DFS - 这可能会失败并找到更长的解决方案。

在标题中使用 BFS 的解决方案是:(这是一个类似 java 的伪代码，需要调整并且可能存在语法错误!)

Queue<Pair, Pair> queue = new LinkedList<>(); //for example
queue.add(new Pair(x,y)); // Tuple is a POJO that holds two integers here
Map<Pair,Pair> parents = new HashMap<>();
parents.put(new Pair(x,y),null);
while (queue.isEmpty() == false) { 
    Pair current = queue.pop();  
    if isTarget(current) return countPathLength(parents, current);
    //assuming you have a isTarget() method that checks if it's the target
    int nextX = current.x - 1;
    int nextY = current.y + 2;
    //missing: make sure (nextX,nextY) is in the board
    if (parents.containsKey(new Pair(nextX,nextY) == false) { 
        parents.put(new Pair(nextX,nextY),current); //you got to the new node from 'current'
        queue.add(new Pair(nextX,nextY),current));
    }
    //repeat for all possible moves
}
return Integer.MAX_VALUE; //no path exist, should be unreachable

private int countPathLength(Map<Pair,Pair> parents, Pair current) {
   int length= 0;
   while (current != null) { 
      length++;
      current = parents.get(current);
   }
   return length;
}

---

作为旁注，由于此处只有一个源和一个目标 - 您甚至可以使用 bi-directional BFS 来增强解决方案，我在 this answer 中对此进行了解释，它还会找到最优解 - 通常比 BFS 更快。