20ms solution, BFS based with reachable detection


  • 0
    C

    My solution is kind of similar to others, basically we start from each building and perform a BFS from there (just use simple BFS, I guess the bottleneck of those testcases is reachable detection). Each time we can get the distance from every empty space to this building and we can merge with the previous results.

    Since there're cases where some buildings are not reachable, we can actually detect those cases during merging. The rule for detection is as follows:

    current[i][j] being min distance of current spot to current building of interest.
    distance[i][j] being global accumulation of min current[i][j]

    1. BFS will mark those unreachable spot from current building to have distance -1
    2. Merging will only update values if grid[i][j] == 0 && distance[i][j] != INT_MAX && current[i][j] != -1, and set flag "reachable" if any of the distance[i][j] is updated.
    3. If current spot is unreachable meaning current[i][j] == -1 and distance[i][j] != INT_MAX, make distance[i][j] = INT_MAX

    In short the principle behind this is that

    If a spot is reachable to all buildings, then during the iteration the spot must be updated each and every merging

    In other words, if one iteration does not update any value, meaning there's no reachable spot to all buildings, we can return -1 from there.

    My solution is not the most concise though, but it's well structured and easy to understand.

    Solution in C++:

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            int n = grid.size();
            int m = grid[0].size();
            vector<vector<int> > board(n, vector<int>(m, 0));
            
            for (int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if (grid[i][j] == 1) {
                        vector<vector<int> > current(n, vector<int>(m, -1));
                        bfs(i, j, current, grid);
                        if (!merge(board, current, grid)) return -1;
                    }
                }
            }
            
            int minPath = INT_MAX;
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (grid[i][j] == 0) {
                        minPath = min(minPath, board[i][j]);
                    }
                }
            }
            
            return minPath == INT_MAX ? -1 : minPath;
        }
        
        bool merge(vector<vector<int> >& board, vector<vector<int> >& current, vector<vector<int>>& grid) {
            int n = board.size();
            int m = board[0].size();
            bool reachable = false;
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (grid[i][j] != 0 || board[i][j] == INT_MAX) continue;
                    if (current[i][j] != -1) {
                        reachable = true;
                        board[i][j] += current[i][j];
                    } else {
                        board[i][j] = INT_MAX;
                    }
                }
            }
            return reachable;
        }
        
        void bfs(int i, int j, vector<vector<int> >& current, vector<vector<int> >& grid) {
            queue<pair<int, int> > order;
            order.push(pair<int, int>(i, j));
            
            while (!order.empty()) {
                int x = order.front().first;
                int y = order.front().second;
                order.pop();
                
                int val = (grid[x][y] != 0) ? 0 : current[x][y];
                
                if (x-1 > -1 && grid[x-1][y] == 0 && current[x-1][y] == -1) {
                    current[x-1][y] = val + 1;
                    order.push(pair<int, int>(x-1, y));
                }
                
                if (y-1 > -1 && grid[x][y-1] == 0 && current[x][y-1] == -1) {
                    current[x][y-1] = val + 1;
                    order.push(pair<int, int>(x, y-1));
                }
                
                if (x+1 < grid.size() && grid[x+1][y] == 0 && current[x+1][y] == -1) {
                    current[x+1][y] = val + 1;
                    order.push(pair<int, int>(x+1, y));
                }
                
                if (y+1 < grid[0].size() && grid[x][y+1] == 0 && current[x][y+1] == -1) {
                    current[x][y+1] = val + 1;
                    order.push(pair<int, int>(x, y+1));
                }
            }
        }
    };
    

Log in to reply
 

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