# 0490. The Maze

<https://leetcode.com/problems/the-maze>

## Description

There is a ball in a `maze` with empty spaces (represented as `0`) and walls (represented as `1`). The ball can go through the empty spaces by rolling **up, down, left or right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the `m x n` `maze`, the ball's `start` position and the `destination`, where `start = [startrow, startcol]` and `destination = [destinationrow, destinationcol]`, return `true` if the ball can stop at the destination, otherwise return `false`.

You may assume that **the borders of the maze are all walls** (see examples).

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg)

```
**Input:** maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
**Output:** true
**Explanation:** One possible way is : left -> down -> left -> down -> right -> down -> right.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/31/maze1-2-grid.jpg)

```
**Input:** maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
**Output:** false
**Explanation:** There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
```

**Example 3:**

```
**Input:** maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
**Output:** false
```

**Constraints:**

* `m == maze.length`
* `n == maze[i].length`
* `1 <= m, n <= 100`
* `maze[i][j]` is `0` or `1`.
* `start.length == 2`
* `destination.length == 2`
* `0 <= startrow, destinationrow <= m`
* `0 <= startcol, destinationcol <= n`
* Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
* The maze contains **at least 2 empty spaces**.

## ac

```java
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int row = maze.length, col = maze[0].length;
        boolean[][] visited = new boolean[row][col];
        return dfs(maze, start[0], start[1], destination, visited);
    }

    private boolean dfs(int[][] maze, int r, int c, int[] dest, boolean[][] visited) {
        // exit, reach destination

        visited[r][c] = true;
        // 4 directions
        for (int i = 0; i < 4; i++) {
            int[] loc = rolling(maze, r, c, i);
            if (loc[0] == dest[0] && loc[1] == dest[1]) return true; // hit the end
            if (visited[loc[0]][loc[1]]) continue; // skip visitd cell
            if (dfs(maze, loc[0], loc[1], dest, visited)) return true; // find one valid path
        }

        return false; // can't find path
    }

    private int[] rolling(int[][] maze, int r, int c, int direction) {
        // 0: up, 1: down, 2:left, 3:right
        if (direction == 0) {
            while (r - 1 >= 0 && maze[r-1][c] == 0) r--;
        } else if (direction == 1) {
            while (r + 1 < maze.length && maze[r+1][c] == 0) r++;
        } else if (direction == 2) {
            while (c - 1 >= 0 && maze[r][c-1] == 0) c--;
        } else if (direction == 3) {
            while (c + 1 < maze[0].length && maze[r][c+1] == 0) c++;
        }

        return new int[]{r, c};
    }
}

/*
just dfs 4 directions, with helper rolling() func
*/
```