Permutations with BFS: Solving Haunted House Contest

[Panphobia]

http://dwite.ca/questions/haunted_house.html
So this is from a contest I wrote a while back, I took the greedy approach for my solution, and I did get 5/5, but my solution was not totally correct because the shortest path was not guaranteed, if a candy was 2 spaces before the start, and a candy was 1 space in front, my algorithm would go to the candy 1 space in front, then to the one 2 spaces back, and then carry on. But to finish this algorithm correctly you would need to figure out all permutations of paths through the candies. So how would I even start to do that? It has been bugging me for a while now.

 

[DimReg]

It's not entirely clear how you attempted to solve it before because you didn't post any sample code, but the type of algorithm used to generate all permutations is called backtracking. (http://en.wikipedia.org/wiki/Backtracking) Maybe you already knew that.

The basic idea is you have a function that takes a partial path, and extends it by one step. Then it calls itself recursively with the new path, once for each possible next step (think of a depth first search). You'll have to add in checks to make sure the path you are considering is valid, but that shouldn't be too difficult.

 

[Panphobia]

So if I went about it with a breadth first search it wouldn't work correct? I can see how a dfs would solve if yes.

 

[DimReg]

Breadth first should do it too, but at far as I know the algorithm is usually depth first. I think it has to do with memory optimization. You only need one path in memory at one time in the depth first approach, which can be helpful if the graph is "wide".

I could be mistaken, but breadth first and depth first should be the same if you are trying to find all paths.

 

[Panphobia]

This is my code in java that works for almost all maps except for something like this
*.B***

import java.io.*;
import java.util.*;

public class CandyBFS {

static int n, candy;
static int minsteps, maxcandy;
static int totCandies = 0;
static boolean[][] is;

public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("C:\\Users\\Daniel\\Desktop\\Java\\CandyBFS\\DATA5.txt"));
    while (s.hasNext()) {
        n = Integer.parseInt(s.nextLine().trim());
        char[][] maze = new char[n][n];
        is = new boolean[n][n];
        int xStart = 0;
        int yStart = 0;
        for (int y = 0; y < n; ++y) {
            String text = s.nextLine().trim();
            for (int x = 0; x < n; ++x) {

                maze[x][y] = text.charAt(x);
                if (maze[x][y] == 'B') {
                    xStart = x;
                    yStart = y;
                }
            }
        }
        candy = 0;
        int tot = 0;
        int y = 0, x = 0;
        x = xStart;
        y = yStart;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                is[i][j] = false;
            }
        }
        while (true) {
            char[][] grid = new char[n][n];
            for (int j = 0; j < n; ++j) {
                for (int i = 0; i < n; ++i) {
                    grid[i][j] = maze[i][j];
                }
            }
            int lol[] = BFS(grid, x, y);
            if (lol[0] == -1) {
                break;
            }
            y = lol[2];
            x = lol[1];
            tot += lol[0];
        }
        System.out.println(candy + " " + tot);
    }
}

public static int[] BFS(char[][] maze, int xStart, int yStart) {
    Queue<int[]> queue = new LinkedList<int[]>();
    int start[] = {xStart, yStart, 0, 0};
    queue.add(start);
    while (queue.peek() != null) {
        int[] array = queue.poll();
        int x = array[0];
        int y = array[1];
        if (x < 0 || y < 0 || y > n - 1 || x > n - 1) {
            continue;
        }
        if (maze[x][y] == '#') {
            continue;
        }
        if (maze[x][y] == '*' && !is[x][y]) {
            is[x][y] = true;
            candy++;
            int sta[] = {array[2], x, y};
            return sta;

        }
        if (maze[x][y] >= 'a' && maze[x][y] <= 'f') {
            if (candy < maze[x][y] - 'a' + 1) {
                continue;
            }
        }
        int[][] points = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        for (int i = 0; i < 4; ++i) {
            int sta[] = {x + points[i][0], y + points[i][1], array[2] + 1};
            queue.add(sta);
        }
        maze[x][y] = '#';
    }
    int sta[] = {-1};
    return sta;
}
}