C++ BFS pruning solution with comments beats 97.09% 6ms


  • 0
    M

    This solution is a basic BFS with two improvements.

    • step1: for each 1, using queue<i, j> and global int visitedMap[i][j] to BFS and get distance to 0
      update total distanceTable[i][j] in all 0s
      update global int canVisitedMap[i][j] to count 1s that has visited 0s and 1s
      Improvement 1: if current 0 is not accessible by previous 1s, skip it.
      Improvement 2: if current 1 is not accessible by previous 1s, return -1
    • step2: find shortest distance in all accessible 0s and return it
    // time complexity: O(n^4), space complexity: O(n^2)
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            // get size
            const int ROW_SIZE = grid.size();
            const int COL_SIZE = grid[0].size();
            // corner case
            if (ROW_SIZE == 0 || COL_SIZE  == 0) {
                return 0;
            }
            // visitedMap[i][j]: how many 1 could pass grid[i][j](0,1) from 1s [0->countBuilding-1]
            // distanceTable[i][j]: total distance to grid[i][j] from 1s [0->countBuilding-1]
            int countOne = 0;
            vector<vector<int> > visitedMap(ROW_SIZE, vector<int>(COL_SIZE, 0));
            vector<vector<int> > distanceTable(ROW_SIZE, vector<int>(COL_SIZE, 0));
            // bfs from each 1 and get the distance to each 0, then add to distanceTable
            // skip all 0s that some of buliding could not visit (countVisitedMap[i][j] < countBuilding)
            for (int i = 0; i < ROW_SIZE; ++i) {
                for (int j = 0; j < COL_SIZE; ++j) {
                    if (grid[i][j] == 1) {
                        if (!helperBFS(grid, i, j, distanceTable, visitedMap, countOne)) {
                            return -1;
                        }
                        countOne++;
                    }
                }
            }
            // find the shortest distance in distanceTable
            int shortestDistance = INT_MAX;
            for (int i = 0; i < ROW_SIZE; ++i) {
                for (int j = 0; j < COL_SIZE; ++j) {
                    if (distanceTable[i][j] > 0 && visitedMap[i][j] == countOne) {
                        shortestDistance = min(shortestDistance, distanceTable[i][j]);
                    }
                }
            }
            return shortestDistance == INT_MAX ? -1 : shortestDistance;
        }
    private:
        bool helperBFS(vector<vector<int> >& grid, int row, int col, vector<vector<int> >& distanceTable,
                       vector<vector<int> >& visitedMap, int countOne) {
            // get size
            const int ROW_SIZE = grid.size();
            const int COL_SIZE = grid[0].size();
            // use queue and visitedMap to bfs
            queue<pair<int, int> > bfsQueue;
            bfsQueue.push({row, col});
            // bfs the shortest distance
            int currDistance = 0;
            while (!bfsQueue.empty()) {
                int size = bfsQueue.size();
                for (int i = 0; i < size; ++i) {
                    // visit current node and update the distance
                    pair<int, int> curr = bfsQueue.front();
                    bfsQueue.pop();
                    distanceTable[curr.first][curr.second] += currDistance;
                    // push all neighbor to the queue
                    int indexList[2][4] = {{-1, 0, 0, 1}, {0, -1, 1, 0}};
                    for (int j = 0; j < 4; j++) {
                        int x = curr.first + indexList[0][j], y = curr.second + indexList[1][j];
                        if (x >= 0 && x < ROW_SIZE && y >= 0 && y < COL_SIZE && visitedMap[x][y] != countOne + 1 && visitedMap[x][y] == countOne) {
                            if (grid[x][y] == 0) {
                                bfsQueue.push({x, y});
                                visitedMap[x][y]++;
                            } else if (grid[x][y] == 1) {
                                visitedMap[x][y]++;
                            }
                        }
                    }
                }
                currDistance++;
            }
            // if there is one 1 could not be accessed, return false
            for (int i = 0; i < ROW_SIZE; ++i) {
                for (int j = 0; j < COL_SIZE; ++j) {
                    if (grid[i][j] == 1 && visitedMap[i][j] != countOne + 1) {
                        return false;
                    }
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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