How to Implement a BFS (instead of my solution, use a tree structure)

Question

I've been working on for a solution for the following question 'http://wcipeg.com/problems/desc/ccc10j5'. Basically, you're given a point on 2D grid (x, y). You must find the shortest path from the starting point to the ending point (which is also given).

Restrictions: You may only travel in an 'L' shape (like a knight in chess).

Although I was able to solve it, people have been telling me that there is a better way to solve it, using a tree structure (or something). Can some help me accelerate my solution.

Here's my code.

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);
        }
    }
}

Thanks in advance.

Please post here the headliens of the exact question, not only a link. — amit, Jan 04 '15 at 16:53

score 1 · Answer 1 · edited May 23 '17 at 12:01

This is a shortest path problem on a graph, and since the graph is unweighted - BFS indeed solves the porblem optimally (finds the closest solution), while your solution is a DFS - which might fail and find a longer solution.

The solution using BFS in head lines is: (this is a java-like pseudo code, tweaking is needed and there might be syntax errors!)

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;
}

As a side note, since there is a single source and a single target in here - you might even enhance the solution using bi-directional BFS, which I explained in this answer, and it will also find optimal solution - and is usually faster than BFS.

How to Implement a BFS (instead of my solution, use a tree structure)

1 Answers1