---
# System prepended metadata

title: 0490. The Maze
tags: [Leetcode, BFS, Medium]

---

# 0490. The Maze
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/the-maze/
## 思路 $O(MN)$ $O(MN)$
这道题没有把visited和maze合并在一起 是因为每次都是走到尽头再跳出while回圈判断
即使中间有哪个点visited过也没有问题
## Code
```java=
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        Queue<int[]> q = new LinkedList<>();
        q.add(start);
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        visited[start[0]][start[1]] = true;
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.isEmpty()){
            int[] curr = q.poll();
            for(int[] dir:dirs){
                int newx = curr[0]+dir[0];
                int newy = curr[1]+dir[1];
                while(newx>=0 && newx<maze.length && newy>=0 && newy<maze[0].length && maze[newx][newy]==0){
                    newx += dir[0];
                    newy += dir[1];
                }
                newx -= dir[0];
                newy -= dir[1];
                if(visited[newx][newy]) continue;
                visited[newx][newy]=true;
                if(newx==destination[0] && newy==destination[1]) return true;
                q.add(new int[]{newx, newy});
            }
        }
        return false;
    }
}

```