Maze

Given a matrix filled with '1's and '0's and only one '9'. Suppose 0 means one can not pass through it and 1 means one can pass. If one can only start at point (0,0), can s/he arrives at the point filled with '9'? (One can only move either up or down or left or right at any point in time.) 

/*
This problem is similar to "Number of Islands", we can use either DFS or BFS to traverse each point start from (0,0) until arriving at 9 or the next paths all being blocked. 
*/

/*
In BFS, there is a tricky way to convert the 2D coordinate into 1D number. And use dx = {1, 0, -1, 0},dy = {0, 1, 0, -1} in the code to avoid redundancy.

BFS: time:O(n^2), space:O(n^2)
*/

import java.util.*;

public class Solution {
    public static int Maze(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || 
            matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        if (matrix[0][0] == 0) {
            return 0;
        }
        if (matrix[0][0] == 9) {
            return 1;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        matrix[0][0] = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            int x = tmp / n;
            int y = tmp % n;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (matrix[nx][ny] == 0) {
                    continue;
                }
                if (matrix[nx][ny] == 9) {
                    return 1;
                }
                queue.add(nx * n + ny);
                matrix[nx][ny] = 0;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};
        int res = Maze(matrix);
        System.out.print(res);
    }

}

//DFS: time:O(n^2), space:O(1)

import java.util.*;

public class Solution {

    public static int Maze(int[][] matrix) {

        if (matrix == null || matrix[0] == null) {

            return 0;

        }

        return dfs(matrix, 0, 0);

    }

    public static int dfs(int[][] matrix, int x, int y) {

        if (x < 0 || x >= matrix.length || 

            y < 0 || y >= matrix[0].length) {

            return 0;

        }

        if (matrix[x][y] == 9) {

            return 1;

        }

        if (matrix[x][y] == 1) {

            matrix[x][y] = 0;

            if (dfs(matrix, x + 1, y) == 1 || 

                dfs(matrix, x, y + 1) == 1 ||

                dfs(matrix, x - 1, y) == 1 || 

                dfs(matrix, x, y - 1) == 1) {

                return 1;

            };

        }

        return 0;

    }

    public static void main(String[] args) {

        int[][] matrix = {{1,1,1},{0,0,1},{9,0,1}};

        int res = Maze(matrix);

        System.out.print(res);

    }

}