Leetcode 490. The Maze

 就是普通的dfs，区别就是选一个方向的时候可以直接走到走不动为止。

时间复杂度： O(n^2), n代表行数

空间复杂度: O(n^2), 用来存储visited二维数组，当然也可以通过改input实现

class Solution {

public:

    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {

        int m = maze.size();

        int n = maze[0].size();

        vector<vector<bool>> visited(m, vector<bool>(n, false));

       

        return dfs(maze, start[0], start[1], destination[0], destination[1], visited);

    }

private:

    bool dfs(vector<vector<int>>& maze, int i, int j, int di, int dj, vector<vector<bool>>& visited) {

        if (i == di && j == dj) {

            return true;

        }

        if (visited[i][j]) {

            return false;

        }

       

        visited[i][j] = true;

       

        vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

       

        for (const auto& dir : directions) {

            int ni = i + dir[0];

            int nj = j + dir[1];

           

            while (ni >= 0 && ni < maze.size() && nj >= 0 && nj < maze[0].size() && maze[ni][nj] == 0) {

                ni += dir[0];

                nj += dir[1];

            }

           

            ni -= dir[0];

            nj -= dir[1];

           

            if (dfs(maze, ni, nj, di, dj, visited)) {

                return true;

            }

        }

       

        return false;

    }

};