search

317 Shortest Distance from All Buildings

Accepted (attempt 2):

The Idea: First collect all the houses within the matrix. Then for each house, BFS on it with the 4 cardinal directions. Additionally, only accept areas that are empty (0). Along the way, output the distances collected onto another matrix, and ensure that the area you step into isn't stepped into again using an additional matrix. Additionally in the BFS, if a house is uncovered, mark it as visited, and remove the house from the collection of houses. Once the BFS algorithm terminates, all the houses should be visited, or in other words, the set that contains all houses should be empty. If not, the matrix is not valid and return -1. Additionally, we may come across a matrix that is valid, but contains blocked off areas only some houses can get to. This this would provide an unfair advantage we collect all the unexplored areas (0's) at the end of the BFS. These areas indicate blocked of areas in the matrix from the perspective of the current house getting BFS'ed on. For these areas, I simply marked them as as obstacle, so that the algorithm I will describe next ignores them. Next, we collect all the BFS'ed matricies, and stack them together into a tensor. Finally, we accumulate the weights of each [i][j][0...k] matrix (where k is the number of houses), and return the minimum result.

Complexity: O(N) space and O(N^2) time where N is the number of elements in matrix.

namespace std {
    template <> struct hash<std::pair<int, int>> {
        inline size_t operator()(const std::pair<int, int> &v) const {
            std::hash<int> int_hasher;
            return int_hasher(v.first) ^ int_hasher(v.second);
        }
    };
}

bool isSteppable(const vector<vector<int>> &visited, const int row, const int col) {
    return (row >= 0 && row < visited.size()
            && col >= 0 && col < visited[row].size()
            && visited[row][col] == 0
        );
}

bool isHouse(const vector<vector<int>> &visited, const int row, const int col) {
    return (row >= 0 && row < visited.size()
        && col >= 0 && col < visited[row].size()
        && visited[row][col] == 1);
}

unordered_set<pair<int, int>> findTargets(vector<vector<int>> &grid, int target) {
    unordered_set<pair<int, int>> stuff;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid.at(i).size(); j++) {
            if (grid[i][j] == target) {
                stuff.insert({ i,j });
            }
        }
    }
    return stuff;
}

// key:
// 0 - empty field
// 1 - house
// 2 - obsticle
// 3 - visited field
// 4 - visited house

tuple<bool, unordered_set<pair<int,int>>, vector<vector<int>>> BFSgrid(const int row, const int col, vector<vector<int>> BFS_grid,
                                        vector<vector<int>> visited, unordered_set<pair<int,int>> houses, 
                                        const vector<function<pair<int, int>(int, int)>> &directions) {

    queue<pair<int, int>> q;

    q.push({ row, col });
    visited[row][col] = 4;
    houses.erase({ row, col });

    while (!q.empty()) {

        pair<int,int> front = q.front();
        q.pop();

        for (auto functor : directions) {
            pair<int, int> next = functor(front.first, front.second);
            if (isSteppable(visited, next.first, next.second)) {
                BFS_grid[next.first][next.second] = BFS_grid[front.first][front.second] + 1;
                visited[next.first][next.second] = 3;
                q.push({next.first, next.second});
            }
            else if (isHouse(visited, next.first, next.second)) {
                visited[next.first][next.second] = 4; // dont want to erase something empty next time
                houses.erase({ next.first, next.second });
            }
        }
    }

    // result whether bfs was valid or not, the blocks that were blocked off, and the bfs grid to accumulate into tensor
    return { houses.empty(), findTargets(visited, 0), BFS_grid };
}

int sumAndFindMin(const vector<vector<vector<int>>> &tensor, const vector<vector<int>> &visited) {

    int minSum = INT_MAX;
    const size_t rows = visited.size();
    const size_t cols = visited.at(0).size();

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (visited[i][j] == 0) {
                int tempSum = 0;
                for (int k = 0; k < tensor.size(); k++) {
                    tempSum += tensor[k][i][j];
                }
                minSum = min(minSum, tempSum);
            }
        }
    }

    return (minSum == INT_MAX) ? -1 : minSum;
}

int shortestDistance(vector<vector<int>>& grid) {

    auto up = [&](int row, int col) {
        return make_pair(--row, col);
    };
    auto down = [&](int row, int col) {
        return make_pair(++row, col);
    };
    auto left = [&](int row, int col) {
        return make_pair(row, --col);
    };
    auto right = [&](int row, int col) {
        return make_pair(row, ++col);
    };

    vector<function<pair<int, int>(int, int)>> cardinalDirections = { up, down, left, right };
    unordered_set<pair<int, int>> houses = findTargets(grid, 1);
    vector<vector<int>> integral_BFS_grid(grid.size(), vector<int>(grid.at(0).size()));

    vector<vector<vector<int>>> tensor;
    tensor.reserve(houses.size());

    for (pair<int,int> p : houses) {
        tuple<bool, unordered_set<pair<int,int>>, vector<vector<int>>> result = BFSgrid(p.first, p.second, 
                                                         integral_BFS_grid, grid, houses, cardinalDirections);
        if (!get<0>(result)) {
            return -1;
        }

        // mark unexplored fields to be invalid (fill in the gaps as an obsticle)
        for (auto i : get<1>(result))
            grid[i.first][i.second] = 2;

        tensor.push_back(get<2>(result));
    }

    return sumAndFindMin(tensor, grid); 
}

Testing

Timed Out Implementation (attempt 1):

  • The approach I took was to run BFS on all valid cells in the grid. BFS works in this case of finding the shortest path, because the 'edge lengths' from cell-to-cell are all the same (0). Each run, I would first ensure that it is an empty cell, then grab the total distance accumulated in the BFS algorithm. As I go, i optimize for the minimum distance found. I also make sure to check for a few things:

    • Visited cells. I maintain a boolean matrix that ensures that I don't repeat going back into a cell (as their obvious cycles).

    • Houses. I do a quick iterative search for all the houses in the grid matrix, and store them as pairs. They will be used to confirm that at the end of the BFS search algorithm that all houses where explored. If not, I return a max integer as an indicator that the algorithm failed in that regard.

    • Bounds: I cannot exceed the size of the grid, neither can I enter obstacles (==2).

  • In the BFS algorithm I maintain a queue that keeps track of the previous level. This will ensure that the next level I enqueue is just 1 above it. I also make sure that if the current cell is on a house, I cannot enqueue the next element (as it is not possible to move from one house to another). In this case, I must return back.

Testing

Previous316 Remove Duplicate LettersNext319 Bulb Switcher

Last updated