-----------------------------------

Panphobia

Sun Nov 25, 2012 12:14 am


Quick DFS prob

-----------------------------------

I might be too tired to realize but I was using a DFS instead of a BFS, since I was having a lot of trouble, on a question, which is this http://dwite.org/questions/shortest_path_around_v2.html , the problem is that when i try to get shortest path for this, [code]........ 
........ 
...##... 
A..##... 
...##... 
...##... 
...##..B 
........[/code] it actually fills it up in this manner and does not output to the  new array the shortest path, i will show [code]3 3 3 3 4 5 6 7 
2 2 2 3 4 5 6 7 
1 1 2 # # 5 6 7 
0 1 2 # # 6 6 7 
1 1 2 # # 7 7 7 
2 2 2 # # 8 8 8 
3 3 3 # # 7 8 9 
4 4 4 4 5 6 7 8 [/code] here is my code, hopefully you guys can see where i failed [code]package bfsv3;

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

public class BFSV3 {

    static int steps = 0;
    static int numSteps[][] = new int[8][8];
    static int finx, finy;

    public static void main(String[] args) throws FileNotFoundException {
        Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFSV3\\src\\bfsv3\\DATA4.txt"));
        for (int q = 0; q < 5; q++) {
            char[][] maze = new char[8][8];
            for (int y = 0; y < 8; y++) {
                String text = s.nextLine();
                for (int x = 0; x < 8; x++) {
                    maze[x][y] = text.charAt(x);
                    numSteps[x][y] = 9999;
                }
            }
            for (int z = 0; z < 8; z++) {
                for (int a = 0; a < 8; a++) {
                    if (maze[a][z] == 'B') {
                        finx = a;
                        finy = z;
                    }
                    if (maze[a][z] == 'A') {
                        //System.out.println(bfs(maze, z, a, '#', 'B') - 1);
                        dfs(a, z, maze, 0, 'B');
                    }
                }
            }
           // System.out.println(finx + " " + finy);
            //System.out.println(numSteps[finx][finy]);
            for (int i = 0; i < 8; i++) {
                for (int a = 0; a < 8; a++) {
                    if(numSteps[a][i]!=9999){
                    System.out.print(numSteps[a][i] + " ");
                    }else{
                        System.out.print("#" + " ");
                    }
                }
                System.out.println();
            }
            System.out.println("\n\n");
        }
    }

    public static void dfs(int x, int y, char[][] maze, int steps, char target) {
        if (maze[x][y] == '#') {
            return;
        }
        //System.out.println(steps+" "+numSteps[x][y]);
            numSteps[x][y] = Math.min(steps,numSteps[x][y]);
        if (steps > numSteps[x][y]) {
            
            
        
            return;
        }
        try {
            if (x > 0 && maze[x - 1][y] != '#') {
                dfs(x - 1, y, maze, steps + 1, target);
            }
            if (x < 8 && maze[x + 1][y] != '#') {
                dfs(x + 1, y, maze, steps + 1, target);
            }
            if (y > 0 && maze[x][y - 1] != '#') {
                dfs(x, y - 1, maze, steps + 1, target);
            }
            if (y < 8 && maze[x][y + 1] != '#') {
                dfs(x, y + 1, maze, steps + 1, target);
            }
            if (x > 0 && y > 0 && maze[x - 1][y - 1] != '#') {
                dfs(x - 1, y - 1, maze, steps + 1, target);
            }
            if (x > 0 && y < 8 && maze[x - 1][y + 1] != '#') {
                dfs(x - 1, y + 1, maze, steps + 1, target);
            }
            if (x < 8 && y < 8 && maze[x + 1][y + 1] != '#') {
                dfs(x + 1, y + 1, maze, steps + 1, target);
            }
            if (x < 8 && y > 0 && maze[x + 1][y - 1] != '#') {
                dfs(x + 1, y - 1, maze, steps + 1, target);
            }
        } catch (Exception e) {
        };
    }
//
//    public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {
//        Queue queue = new LinkedList();
//        int[] start = {yStart, xStart, 0};
//        queue.add(start);
//        while (queue.peek() != null) {
//            int[] array = queue.remove();
//            int x = array[0];
//            int y = array[1];
//            if (x < 0 || x >= 8 || y < 0 || y >= 8) {
//                continue;
//            }
//            if (maze[x][y] == wall) {
//                continue;
//            }
//            if (maze[x][y] == goal) {
//                return array[2] + 1;
//            }
//
//            int[][] newPoints = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
//            //int[][] newPoints = {{-1,-1},{-1,1},{1,-1},{1,1}}; 
//            for (int i = 0; i < 8; i++) {
//                int[] temp = {x + newPoints[i][0], y + newPoints[i][1], array[2] + 1};
//                queue.add(temp);
//            }
//            maze[x][y] = wall;
//        }
//
//        return 0;
//
//    }
}[/code]


-----------------------------------

mirhagk

Sun Nov 25, 2012 1:39 am


RE:Quick DFS prob

-----------------------------------

you're algorithm isn't DFS, it's Dijkstra's and it doesn't even attempt to find the shortest path. You have your answer in the output, you're just really not even trying to use it for some reason.....

[code]
numSteps[x][y] = Math.min(steps,numSteps[x][y]); 
if (steps > numSteps[x][y]) { 
            return; 
}
[/code]
Will that return statement ever be reached?