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 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:
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:
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:
1 <= maze.length, maze[i].length <= 100
maze[i][j]
is0
or1
.start.length == 2
destination.length == 2
0 <= startrow, destinationrow <= maze.length
0 <= startcol, destinationcol <= maze[i].length
- Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
- The maze contains at least 2 empty spaces.
A:
DFS
就是每次不直接找到下一个节点。 而是找到所有的靠墙的节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { int m = maze.size(); int n = maze[0].size(); if(start == destination) return true; if(maze[start[0]][start[1]] !=0){ return false; } maze[start[0]][start[1]] = -1; vector<vector<int>> Diff{{1,0},{-1,0}, {0,1}, {0,-1}}; for(auto d : Diff){ auto pre = start; while(true){ auto next = vector<int>{pre[0]+d[0], pre[1] + d[1]}; if(next[0]>= 0 && next[0] <m && next[1] >=0 & next[1] < n && maze[next[0]][next[1]] != 1){ pre = next; }else{ break; } } if(maze[pre[0]][pre[1]] == 0){ auto res = hasPath(maze, pre, destination); if(res) return true; } } return false; } }; |
犯的错误:
一开始没有看懂题意,还 以为是所有经过的都可以呢。
*************** solution 2 ****既然只能靠墙的才能算,那我们只grow*********
No comments:
Post a Comment