Dfs solution C++


  • 0
    X
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            if (rooms.size() == 0) return;
            int m = rooms.size(), n = rooms[0].size();
            vector<pair<int, int>> moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (rooms[i][j] == 0)
                        dfs(rooms, i, j, m, n, moves, 0);
        }
        
        void dfs(vector<vector<int>>& rooms, int i, int j, int m, int n, vector<pair<int, int>>& moves, int curDistance) {
            if (!inside(i, j, m, n)) return;
            
            if (rooms[i][j] > 0)
                rooms[i][j] = min(rooms[i][j], curDistance);
            
            for (auto move : moves) {
                if (inside(i + move.first, j + move.second, m, n) && rooms[i + move.first][j + move.second] > curDistance + 1)
                    dfs(rooms, i + move.first, j + move.second, m, n, moves, curDistance + 1);
            }
        }
        
        bool inside(int i, int j, int m, int n) {
            return i >= 0 && i < m && j >= 0 && j < n;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.