Quick DFS prob

Panphobia · **Posted:** Sun Nov 25, 2012 12:14 am

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
........

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

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<int[]> queue = new LinkedList<int[]>();
// 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;
//
// }
}

mirhagk · **Posted:** Sun Nov 25, 2012 1:39 am

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

Will that return statement ever be reached?

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members