C++ Non-recursive DFS solution


  • 0
    A

    Start searching from coast. Do the same for each ocean.
    The check on 4 neighbors can be folded into a loop using offsets, but I find that actually makes it a little slower than current unfolded form.

    113 / 113 test cases passed
    Status: Accepted
    Runtime: 59 ms

    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            int h = matrix.size() - 1, w = h > -1 ? matrix[0].size() - 1 : -1;
            vector<pair<int, int>> res;
            if (h < 0) return res;
            vector<vector<unsigned char>> visited(h+1, vector<unsigned char>(w+1, 0));
            stack<array<uint, 2>> stk;
            for (unsigned char mask = 0x1; mask <= 0x2; mask++) {
                uint k = mask == 0x1 ? 0 : w;
                for (uint i = 0; i <= h; i++) {
                    visited[i][k] |= mask;
                    stk.push({i, k});
                }
                k = mask == 0x1 ? 0 : h;
                for (int j = mask == 0x1 ? 1 : 0, jj = mask == 0x1 ? w : w-1; j <= jj; j++) {
                    visited[k][j] |= mask;
                    stk.push({k, j});
                }
                while (!stk.empty()) {
                    uint x = stk.top()[0], y = stk.top()[1], val = matrix[x][y];
                    stk.pop();
                    if (x && !(visited[x-1][y] & mask) && matrix[x-1][y] >= val) {
                        visited[x-1][y] |= mask;
                        stk.push({x-1, y});
                    }
                    if (x < h && !(visited[x+1][y] & mask) && matrix[x+1][y] >= val) {
                        visited[x+1][y] |= mask;
                        stk.push({x+1, y});
                    }
                    if (y && !(visited[x][y-1] & mask) && matrix[x][y-1] >= val) {
                        visited[x][y-1] |= mask;
                        stk.push({x, y-1});
                    }
                    if (y < w && !(visited[x][y+1] & mask) && matrix[x][y+1] >= val) {
                        visited[x][y+1] |= mask;
                        stk.push({x, y+1});
                    }
                }
            }
            for (uint i = 0; i <= h; i++) {
                for (uint j = 0; j <= w; j++) {
                    if (visited[i][j] == 0x3) res.emplace_back(i, j);
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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