JAVA 使用堆栈和无节点的迷宫 DFS 中的老鼠

Question

我是一名学生，正在学习JAVA。我确实为 DFS（迷宫中的老鼠）编写了代码，我需要使用堆栈。我不想要 Node class 并且我的迷宫只是最终的。 [0][0] 是开始，[5][5] 是出口，其中有 'e'.

所以，这是我的代码，但如果我运行这段代码，则 (1, 3), (2, 1) 之间存在声誉。为什么此代码失败？

import java.util.Stack;

public class MazeSearch {

public static final int N = 6;
boolean[][] isVisited = new boolean[N][N];

public static int[][] maze = {
        {0, 1, 1, 1, 1, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 0, 0, 1, 1},
        {1, 0, 1, 0, 1, 1},
        {1, 0, 1, 0, 0, 1},
        {1, 1, 1, 1, 0, 'e'},               
};



public static void main(String[] args) {    
    
    if (dfs(maze, 0, 0))
        System.out.println("Success!");
    else
        System.out.println("Failed!");
    
}

public static boolean isValid(int m[][], int x, int y) {
    
    if (x< 0 || y<0 || x>= N || y>= N)
        return false;
    else
        return (m[y][x] == 0 || m[y][x] == 2);
        
    
}

public static boolean dfs(int m[][], int x, int y) {        
    
    Stack<Integer> stack = new Stack<Integer>();
    
    stack.push(x);
    stack.push(y);
    
    while(!stack.isEmpty())
    {
        int curx = stack.pop();
        int cury = stack.pop();
        
        System.out.printf("(" + curx + " " + cury + ")" + " -> ");
        
        if (m[cury][curx] == 2)
        {
            System.out.println("dfs searching complete!");
            return true;
        }
        else
        {
            m[cury][curx] = ',';
            
            if (isValid(m, curx, cury-1)) {
                stack.push(curx);
                stack.push(cury-1);
            }
            else if (isValid(m, curx, cury+1)) {
                stack.push(curx);
                stack.push(cury+1);
            }
            else if (isValid(m, curx-1, cury)) {
                stack.push(curx-1);
                stack.push(cury);
            }
            else if (isValid(m, curx+1, cury)) {
                stack.push(curx+1);
                stack.push(cury);
            }
            System.out.printf("content of stack (now): (%d, %d)\n", curx, cury);
        }
        
    }
    
    return false;
    }

}

编辑：现在我修复了一些东西，效果很好。

Answer 1

一些注意事项：

堆栈工作 后进先出 (LIFO)，所以，因为您对 x 和 y 使用相同的堆栈坐标，请注意在这种情况下 poping 应该与 pushing 相反，即如果您先 push x 坐标然后 y 然后y 应该在最上面，所以你应该先 pop y 坐标，然后 x.

对于每个访问的网格单元，您只将一个相邻的网格单元推入堆栈。但是每个网格单元有 4 个邻居，而不是 1 个。所以你应该检查每次访问的所有邻居，这意味着转换它：

if (isValid(m, curx, cury-1)) {
    stack.push(curx);
    stack.push(cury-1);
}
else if (isValid(m, curx, cury+1)) {
    stack.push(curx);
    stack.push(cury+1);
}
else if (isValid(m, curx-1, cury)) {
    stack.push(curx-1);
    stack.push(cury);
}
else if (isValid(m, curx+1, cury)) {
    stack.push(curx+1);
    stack.push(cury);
}

对此：

if (isValid(m, curx, cury-1)) {
    stack.push(curx);
    stack.push(cury-1);
}
if (isValid(m, curx, cury+1)) {
    stack.push(curx);
    stack.push(cury+1);
}
if (isValid(m, curx-1, cury)) {
    stack.push(curx-1);
    stack.push(cury);
}
if (isValid(m, curx+1, cury)) {
    stack.push(curx+1);
    stack.push(cury);
}

（基本上删除 elses）。

您没有使用 isVisited 数组。对于您访问的每个网格单元格，您可以将相应的位置设置为 true 并在 isValid 逻辑中使用此信息，以便从中 return false 如果给定的单元格已经访问过。

总结笔记，如下示例代码：

import java.util.Stack;

public class MazeSearch {

    public static final int N = 6;
    private static boolean[][] isVisited = new boolean[N][N];

    public static char[][] maze = {
        {'0', '1', '1', '1', '1', '1'},
        {'0', '0', '1', '0', '0', '1'},
        {'1', '0', '0', '0', '1', '1'},
        {'1', '0', '1', '0', '1', '1'},
        {'1', '0', '1', '0', '0', '1'},
        {'1', '1', '1', '1', '0', 'e'}};

    public static void main(String[] args) {
        if (dfs(maze, 0, 0)) {
            System.out.println("Success!");
        } else {
            System.out.println("Failed!");
        }

    }

    public static boolean isValid(char m[][], int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N)
            return false;
        if (isVisited[y][x])
            return false;
        return (m[y][x] == '0' || m[y][x] == '2');
    }

    public static boolean dfs(char m[][], int x, int y) {

        Stack<Integer> stack = new Stack<>();

        stack.push(x);
        stack.push(y);

        while (!stack.isEmpty()) {
            //Changed the pop sequence!
            int cury = stack.pop();
            int curx = stack.pop();

            System.out.println("Visiting [" + cury + ", " + curx + "]...");

            if (m[cury][curx] == '2') {
                System.out.println("dfs searching complete!");
                return true;
            } else {
                m[cury][curx] = ',';
                isVisited[cury][curx] = true;

                if (isValid(m, curx, cury - 1)) {
                    stack.push(curx);
                    stack.push(cury - 1);
                }
                if (isValid(m, curx, cury + 1)) {
                    stack.push(curx);
                    stack.push(cury + 1);
                }
                if (isValid(m, curx - 1, cury)) {
                    stack.push(curx - 1);
                    stack.push(cury);
                }
                if (isValid(m, curx + 1, cury)) {
                    stack.push(curx + 1);
                    stack.push(cury);
                }
                //System.out.printf("content of stack (now): (%d, %d)\n", curx, cury);
            }

        }
        return false;
    }
}

尝试将字符从 '0' 更改为 '2'（在迷宫中），您将看到 Success 消息（因为您找到了它）。否则，您将在控制台中看到所有索引都已访问，但由于未找到 '2'，因此您将按预期看到 Failure 消息。

JAVA 使用堆栈和无节点的迷宫 DFS 中的老鼠

JAVA rat in a maze DFS using stack and no node

java

search

maze

depth-first-search