787. The Maze
https://www.cnblogs.com/grandyang/p/6381458.html
与number of island不一样，递归的函数返回值是bool，不是void。
maze = -1用来表示已经访问的节点。
dp用来记录每个位置的是否能访问，如果dp != -1，就表示这个地方已经访问过了，可以避免多余的访问。
一直滑动用while循环来做，这里并没有没移动一次就增加一个访问。
int x = i,y = j必须这样写，因为之后的4种迭代都是从i、j这个位置出发，x、y在每一次迭代过程中已经发生了变化。
vector的初始化用{}，如果是vector<vector<int>>，初始化用{{},{},{}}
class Solution { public: /** * @param maze: the maze * @param start: the start * @param destination: the destination * @return: whether the ball could stop at the destination */ bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) { // write your code here int m = maze.size(); if(m <= 0) return false; int n = maze[0].size(); if(n <= 0) return false; vector<vector<int>> dp(m,vector<int>(n,-1)); return hasPath(maze,dp,start[0],start[1],destination[0],destination[1]); } bool hasPath(vector<vector<int>>& maze,vector<vector<int>>& dp,int i,int j,int di,int dj){ if(i == di && j == dj) return true; if(dp[i][j] != -1) return dp[i][j]; maze[i][j] = -1; int m = maze.size(),n = maze[0].size(); bool res = false; for(auto dir : dirs){ int x = i,y = j; while(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != 1){ x += dir[0]; y += dir[1]; } x -= dir[0]; y -= dir[1]; if(maze[x][y] != -1) res |= hasPath(maze,dp,x,y,di,dj); } return res; } vector<vector<int>> dirs{{0,-1},{1,0},{0,1},{-1,0}}; };
788. The Maze II
lintcode 787. The Maze 、788. The Maze II 、
原文：https://www.cnblogs.com/ymjyqsx/p/10848694.html