Как реализовать 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 действительно решает porblem оптимально (находит ближайший раствор), в то время как ваше решение является 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.