lintcode 787. The Maze 、788. The Maze II 、

佚名 6年前 (2019-05-11) 随笔 1320人围观抢沙发百度已收录

787. The Maze

https://www.cnblogs.com/grandyang/p/6381458.html

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

与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}};
};