3

好的，所以我开始研究这个问题http://dwite.ca/questions/shortest_path_around_v2.html，我从两个角度看待它，DFS/BFS，现在我想问为什么我的 DFS/BFS 在这里都不起作用是我的 BFS 和 DFS 代码，BFS 也提供输出但不是最短路径，它只提供 A 路径

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 {
    //        here is my input 
    //........
    //........
    //...##...
    //A..##...
    //...##...
    //...##...
    //...##..B
    //........
    //and this is the output for the dfs, as you can see where B is it doesnt give 8 but 9
    //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 
    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) {
            dfs(x - 1, y, maze, steps + 1, target);
        }
        if (x < 8) {
            dfs(x + 1, y, maze, steps + 1, target);
        }
        if (y > 0) {
            dfs(x, y - 1, maze, steps + 1, target);
        }
        if (y < 8) {
            dfs(x, y + 1, maze, steps + 1, target);
        }
        if (x > 0 && y > 0) {
            dfs(x - 1, y - 1, maze, steps + 1, target);
        }
        if (x > 0 && y < 8) {
            dfs(x - 1, y + 1, maze, steps + 1, target);
        }
        if (x < 8 && y < 8) {
            dfs(x + 1, y + 1, maze, steps + 1, target);
        }
        if (x < 8 && y > 0) {
            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;

}
}
4

1 回答 1

1

  1. 文件系统：

    您正在检查迷宫超出范围的限制。（ if (x < 8)例如，但您的迷宫被声明为char[][] maze = new char[8][8];

    这会生成一个java.lang.ArrayIndexOutOfBoundsException，但是由于空的 catch 块，这个异常不会被抛出任何地方：

    } catch (Exception e)
{
};

    在dfs方法结束时

    请不要做这种事！（为什么空的 catch 块是个坏主意？）

    此外，这打破了你的递归。

  2. BFS：我认为使用 的辅助数组更容易理解int's，至少对于测试而言。

无论如何，在这里你有你发布的代码的修改工作版本：

package rpax.stackoverflow.maze13549150;

import java.io.File;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main13549150 {

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

    public static void main(String[] args) {
        try
        {

            Scanner s = new Scanner(new File("files/files13549150/DATA4.txt"));
            // for (int q = 0; q < 5; q++)
            // { // I dont know the reason of this loop - Maybe more files?
            char[][] maze = new char[8][8];
            System.out.println("MAZE: ");
            for (int y = 0; y < 8; y++)
            {
                String text = s.nextLine();
                for (int x = 0; x < 8; x++)
                {
                    maze[x][y] = text.charAt(x);
                    System.out.print(maze[x][y] + " ");
                    numSteps[x][y] = Integer.MAX_VALUE;
                }
                System.out.println();
            }
            System.out.println();
            outer:
            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: ");
                        System.out.println(bfs2(maze, a, z, '#', 'B'));
                        dfs(a, z, maze, 0, 'B');
                        break outer;
                    }
                }
            }
            System.out.println("DFS: ");
            for (int y = 0; y < 8; y++)
            {

                for (int x = 0; x < 8; x++)
                {
                    if (maze[x][y] == '#')
                    {

                        System.out.print('#' + " ");
                    }

                    else
                        System.out.print(numSteps[x][y] + " ");
                }
                System.out.println();
            }

        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }

    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)
        {
            dfs(x - 1, y, maze, steps + 1, target);
        }
        if (x < 7)
        {
            dfs(x + 1, y, maze, steps + 1, target);
        }
        if (y > 0)
        {
            dfs(x, y - 1, maze, steps + 1, target);
        }
        if (y < 7)
        {
            dfs(x, y + 1, maze, steps + 1, target);
        }
        if (x > 0 && y > 0)
        {
            dfs(x - 1, y - 1, maze, steps + 1, target);
        }
        if (x > 0 && y < 7)
        {
            dfs(x - 1, y + 1, maze, steps + 1, target);
        }
        if (x < 7 && y < 7)
        {
            dfs(x + 1, y + 1, maze, steps + 1, target);
        }
        if (x < 7 && y > 0)
        {
            dfs(x + 1, y - 1, maze, steps + 1, target);
        }
        // try to avoid this kind of things -> bad practice + breaks recursion
        // } catch (Exception e) {
        // };
    }

    public static int bfs2(char[][] maze, int yStart, int xStart, char wall,
            char goal) {
        Queue<int[]> queue = new LinkedList<int[]>();
        int[] start = { yStart, xStart, 0 };
        int[][] res = new int[8][8];
        int distanceToGoal = Integer.MAX_VALUE;
        for (int i = 0; i < res.length; i++)
        {
            for (int j = 0; j < res.length; j++)
            {
                res[i][j] = Integer.MAX_VALUE;
            }
        }

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

            // already explored
            if (array[2] >= res[x][y])
            {
                continue;
            }
            res[x][y] = array[2];

            if (maze[x][y] == goal)
            {
                distanceToGoal = array[2] + 1;
                break;
            }

            int[][] newPoints = { { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 },
                    { -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);
            }

        }
        // testing
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {

                if (maze[j][i] == wall)
                {
                    System.out.print("#" + " ");
                }
                else if (res[j][i] != Integer.MAX_VALUE)
                    System.out.print(res[j][i] + " ");
                else // if not explored
                    System.out.print("." + " ");
            }
            System.out.println();
        }
        return distanceToGoal;

    }
}

输出：

MAZE: 
. . . . . . . . 
. . . . . . . . 
. . . # # . . . 
A . . # # . . . 
. . . # # . . . 
. . . # # . . . 
. . . # # . . B 
. . . . . . . . 

BFS: 
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 # # 7 7 . 
3 3 3 # # 6 7 8 
4 4 4 4 5 6 7 8 
9
DFS: 
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 # # 7 7 8 
3 3 3 # # 6 7 8 
4 4 4 4 5 6 7 8
于 2014-05-05T10:05:00.480 回答