Build Post Office II

update Jul 19, 2017 16:49

lintcode

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.

Return the smallest sum of distance. Return -1 if it is not possible.

Notice

You cannot pass through wall and house, but can pass through empty.
You only build post office on an empty.

Example Given a grid:

0 1 0 0 0
1 0 0 2 1
0 1 0 0 0

return 8, You can build at (1,1). (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

Basic Idea:

方法1:从空格出发 循环枚举所有的office修建位置的可能性(空格) 计算从这个位置出发到达所有房子的距离之和 在所有方案中找到最小的距离和

方法2:从房子出发 循环枚举所有的房子的位置 从房子出发,计算每个空格到达房子的距离 累加某个空格到达其他所有房子的距离之和 在所有空格中,找到最小距离和

以上是九章中提出的用来讨论的两种方式，其实从时间复杂度的角度考虑，如果房子的数量等于空地数量，两种方法是差不多的。但是就这道题而言，方法二会好一些，因为房子的数量相对较少。整个方法的实现有些细节需要关注，但整体其实比较无脑。

具体的，需要记录每个空格到所有房子的距离和，以及每个空格能否被所有房子reach。选择能被所有房子reach的最小距离和的空格即可。

Java Code:

    public class Solution {
        /**
         * @param grid a 2D grid
         * @return an integer
         */

        private int[][] grid;
        private int R, C;
        private int WALL = 2;
        private int HOUSE = 1;
        private int EMPTY = 0;
        private int[] dx = new int[]{1, 0, -1, 0};
        private int[] dy = new int[]{0, 1, 0, -1};

        public int shortestDistance(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
            setGrid(grid);
            List<int[]> houses = getCords(HOUSE);
            int[][] distanceSum = new int[R][C];
            int[][] visTimes = new int[R][C];
            for (int[] house : houses) {
                bfs(house, distanceSum, visTimes);
            }
            int minDistanceSum = Integer.MAX_VALUE;
            List<int[]> emptys = getCords(EMPTY);

            for (int[] empty : emptys) {
                int m = empty[0];
                int n = empty[1];
                if (visTimes[m][n] != houses.size()) continue;
                minDistanceSum = Math.min(minDistanceSum, distanceSum[m][n]);
            }
            if (minDistanceSum == Integer.MAX_VALUE) return -1;
            return minDistanceSum;
        }

        private void setGrid(int[][] grid) {
            this.grid = grid;
            R = grid.length;
            C = grid[0].length;
        }

        private List<int[]> getCords(int type) {
            List<int[]> ret = new ArrayList<>();
            for (int i = 0; i < R; ++i) {
                for (int j = 0; j < C; ++j) {
                    if (grid[i][j] == type) {
                        ret.add(new int[]{i, j});
                    }
                }
            }
            return ret;
        }

        private boolean isValid(int[] cord) {
            int r = cord[0], c = cord[1];
            if (r < 0 || r >= R || c < 0 || c >= C) {
                return false;
            }
            return true;
        }

        // 用distanceSum来记录每个空地的距离和，用visTimes记录每个空地可以被几个房子
        // 接触，如果不能被所有房子接触的空地就不予考虑最终位置。
        private void bfs(int[] cord, int[][] distanceSum, int[][] visTimes) {
            Deque<int[]> queue = new LinkedList<>();
            queue.addFirst(cord);
            boolean[][] visited = new boolean[R][C];
            int distance = 0;
            while (! queue.isEmpty()) {
                int size = queue.size();
                distance++;
                for (int i = 0; i < size; ++i) {
                    int[] rc = queue.removeLast();
                    for (int j = 0; j < 4; ++j) {
                        int m = rc[0] + dx[j];
                        int n = rc[1] + dy[j];
                        if (! isValid(new int[]{m, n})) continue;
                        if (visited[m][n]) continue;
                        if (grid[m][n] == 0) {
                            // visit
                            visTimes[m][n]++;
                            distanceSum[m][n] += distance;
                            visited[m][n] = true;
                            queue.addFirst(new int[]{m, n});
                        }
                    }
                }
            }
        }
    }

update 2018-05-22 20:55:37

C++ Code

这次的实现和之前java实现的结构略有不同，感觉这次的更加利于理解：

    class Solution {
    public:
        /**
         * @param grid: a 2D grid
         * @return: An integer
         */

        const int EMPTY = 0;
        const int HOUSE = 1;
        const int WALL = 2;
        const int dr[4]{-1, 0, 1, 0};
        const int dc[4]{0, -1, 0, 1};

        int shortestDistance(vector<vector<int>> &grid) {
            vector<vector<int>> dists(grid.size());
            vector<vector<int>> visitTimes(grid.size());
            for (int i = 0; i < grid.size(); ++i) {
                dists[i].resize(grid[0].size());
                visitTimes[i].resize(grid[0].size());
            }
            auto& houses = getCoords(grid, HOUSE);
            auto& empties = getCoords(grid, EMPTY);

            computeDist(grid, houses, visitTimes, dists);

            int ret = 0x7fffffff;
            for (auto& coord : empties) {
                int r = coord.first, c = coord.second;
                if (visitTimes[r][c] != houses.size()) continue;
                ret = min(ret, dists[r][c]);
            }

            return ret == 0x7fffffff ? -1 : ret;
        }

        // 获取house或者empty的全部坐标pair
        vector<pair<int, int>>& getCoords(vector<vector<int>>& grid, int type) {
            vector<pair<int, int>>& ret = *(new vector<pair<int, int>>());
            for (int r = 0; r < grid.size(); ++r) {
                for (int c = 0; c < grid[0].size(); ++c) {
                    if (grid[r][c] == type) ret.push_back(make_pair(r, c));
                }
            }
            return ret;
        }

        // 计算从每个house出发到所有empty的距离，更新dists为每个empty到所有house的距离和
        // 并且在 visitTimes 中记录每个 empty 被 visit 的次数，如果一个empty的次数小于house
        // 数量，说明它不能被所有房子reach到，则不考虑该位置
        void computeDist(vector<vector<int>>& grid, vector<pair<int, int>>& houses, 
            vector<vector<int>>& visitTimes, vector<vector<int>>& dists) {
            for (auto& coord : houses) {
                // bfs 计算该house到所有empty的距离
                vector<vector<bool>> visited(grid.size());
                for (vector<bool>& v : visited) v.resize(grid[0].size());
                deque<pair<int, int>> _queue;
                _queue.push_back(coord);
                int step = 1;
                while (! _queue.empty()) {
                    int size = _queue.size();
                    for (int i = 0; i < size; ++i) {
                        auto& currCoord = _queue.front();
                        _queue.pop_front();
                        for (int j = 0; j < 4; ++j) {
                            int r = currCoord.first + dr[j], c = currCoord.second + dc[j];
                            if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size()) continue;
                            else if (grid[r][c] == WALL || grid[r][c] == HOUSE) continue;
                            else if (visited[r][c]) continue;
                            _queue.push_back(make_pair(r, c));
                            dists[r][c] += step;
                            visitTimes[r][c]++;
                            visited[r][c] = true;
                        }
                    }
                    ++step;
                }
            }
        }
    };