JAVA rat in a maze DFS using stack and no node-CodePudding

I am a student and studying JAVA. I did write my code for DFS (Rat in a maze) and I need to use stack. I don't want Node class and my maze is just final. [0][0] is start and [5][5] is exit which has 'e'.

So, here's my code but if I run this code, there is a reputation between (1, 3), (2, 1). why this code failed?

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

}

EDIT: Now I repair some things and it works well.

CodePudding user response：

Some notes:

Stacks work Last-In-First-Out (LIFO), so, because you are using the same stack for both x and y coordinates, note that poping should be the opposite of pushing in this case, ie if you push the x coordinate first and then the y then y is expected to be on top, so you should pop the y coordinate first and then the x.

You push only one neighbouring grid cell into the stack for each visited grid cell. But each grid cell has 4 neighbours, not 1. So you should check all neighbours for each visit, which means converting this:

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

to this:

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

(basically removing the elses).

You don't use the isVisited array. For each grid cell you visit, you can set the corresponding location to true and use this information in isValid logic, so as to return false from it if the given cell is already visited.

Summarizing the notes, follows example code:

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

Try changing a character from '0' to '2' (in the maze) and you will see the Success message (because you found it). Otherwise you will see in the console that all indices are visited, but because no '2' will be found then you will see Failure message as expected.