Finding the "cheese" in an array maze

You're given an mxn array. The number 9 is the cheese, the number 0 is a wall and the number 1 is a path. You are the mouse and start in the top left corner a[0][0]. You need to find out whether there is a path to the cheese. This is the question I was given. I tried solving it a certain way and I was wondering if anyone could tell me whether it was correct or on the right path because I kind of thought of it spur of the moment and ran out of time on the test.

My thinking is that if you know you start at the top left corner, then you only need to move down and right if the array looks like this:

So the top left corner is a 1, that means a path exists, so what I did was recurse on the top left corner provided by the adjacent cells to the right and left, creating 2 subarrays. so I called the isPath method on these two subarrays

and then on

1 1 0 0 
0 1 1 9
0 0 0 0

A basic version of the method looked like this:

isPath(int[][] matrix) {
    if(matrix[0][0] == 0)
        return 0;
    if(matrix[0][0] == 9)
        return 1; //found
    if(matrix[0][0] == 1) {
        subarray1 = copy starting from matrix[0][1]
        subarray2 = copy starting from matrix[1][0]
        isPath(subarray1)
        isPath(subarray2)
    }
}

Is this the right way to solve this? Or am I missing something

EDIT: No helper methods

Solution

I think you forget array like this:

your recursive function will not be finished in the previous example, please check the size of array to finish recursion.

Also your algorithm does not use up and right to find cheese

EDIT

you should handle the 4 directions, and don't repeat the square you visit before, I will add pseudo code here to explain the main idea of solution:

public class MAZE {

    static int x, y;
    static boolean result = false;

    public static void main(String[] args) {
        int [][] matrix =new int[5][];// fill your array
        // fill x and y
        // x= cheese x value
        // y = cheese y value
        isPath(matrix, x, x);
        // print result


    }

    static void isPath(int[][] matrix, int i, int j) {
        if (i - 1 > -1 && matrix[i - 1][j] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i-1][j]
            // checkSPath(subarray1,i-1,j);
        }
        if (j - 1 > -1 &&  matrix[i][j - 1] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i][j-1]
            // checkLPath(subarray1,i,j-1);
        }

        if (i + 1 < x && matrix[i + 1][j] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i+1][j]
            // checkNPath(subarray1,i+1,j);
        }
        if (j + 1 < y &&  matrix[i][j + 1] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i][j+1]
            // checkRPath(subarray1,i,j+1);
        }
    }

    static void checkRPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1,i,j+1);
            }
        }
    }

    static void checkLPath(int[][] matrix, int i, int j) {

        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1,i,j-1);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
        }
    }

    static void checkNPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1,i,j-1);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1,i,j+1);
            }
        }

    }

    static void checkSPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1);
            }

            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1);
            }
        }
    }
}

You can merge these 5 methods in one. here I am trying to explain the solution not writing optimized code.