C++ DFS

Leetcode 490. The Maze

Jimmy (xiaoke) Shen

·

Follow

1 min read

·

Aug 23, 2020

--

1

Share

490. The Maze

//int visited[110][110];
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
class Solution {
public:
    bool dfs(vector<vector<int>>& maze,vector<vector<int>>& seen, int i, int j, int desi, int desj) {
        const int R = maze.size(), C = maze[0].size();
        seen[i][j] = 1;
        if (i==desi && j == desj) return true;
        for (int d = 0; d < 4; ++d) {
            int r = i, c = j;
            while (true) {
                r  += di[d], c  += dj[d];
                if (r >= R || r < 0 || c >= C || c < 0 || maze[r][c] == 1) {
                    r -= di[d];
                    c -= dj[d];
                    break;
                }
            }
            if (seen[r][c] == 0) {
                if (dfs(maze, seen, r, c, desi, desj)) return true;
            }
        }
        return false;
    }
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        const int R = maze.size(), C = maze[0].size();
        vector<vector<int>> seen(R, vector<int>(C, 0));
        return dfs(maze, seen, start[0], start[1], destination[0], destination[1]); 
    }
};