> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/untitled.md).

# Rat in a Maze

You are given a r**ectangular maze - where 0s represent obstacles and 1s represent valid passage**. There is a "player" sitting in top-left and intends to reach bottom-right. The "player" can move top, left, bottom or right but only 1 step at a time. The "player" can't pass through an obstacle. Besides, you are given a limit on the number of moves allowed. You've to find out whether the "player" can reach destination honoring the rules of game within **maximum permitted moves**. Input Format

N (integer) - size of 2-d array 

N \* N integers - row-by-row data for the maze (1s and 0s) 

Limit (integer) - maximum number of moves permitted Constraints

0 <= N <= 1000&#x20;

0 <= Aij < 10^9&#x20;

0 <= Limit <= N \* N&#x20;

**Output Format:**

true or false&#x20;

**Sample Input 0:**

4 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 5&#x20;

**Sample Output 0:**

false

```java
class Solution {
    static int moves[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

    public boolean isPossible(int n, int[][] maze, int limit) {
        boolean[][] visited = new boolean[n][n];
        return helper(n, maze, limit, 0, 0, visited);
    }

    public static boolean helper(int n, int[][] arr, int limit, int R, int C, boolean[][] visited) {
        if (limit == 0) {
            if (R == n - 1 && C == n - 1)
                return true;
            return false;
        }
        if (R >= 0 && R < n && C >= 0 && C < n && arr[R][C] == 1 && !visited[R][C]) {
            visited[R][C] = true;
            boolean ans = false;
            for (int[] move : moves) {
                ans = ans || helper(n, arr, limit - 1, R + move[0], C + move[1], visited);
                if (ans)
                    break;
            }
            visited[R][C] = false;
            return ans;
        }
        return false;
    }
}
```