1162.As Far from Land as Possible¶

1162.As Far from Land as Possible¶

Tags: Medium Breadth-first Search

Links: https://leetcode.com/problems/as-far-from-land-as-possible/

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

class Solution {
    vector<vector<int>> used;
    int m, n;
    int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
public:
    struct Node {
        int x, y;
        Node(int xEle, int yEle) : x(xEle), y(yEle) {}
    };

    int maxDistance(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        m = grid.size(), n = grid[0].size();
        used.resize(m, vector<int>(n, -1));

        int maxDistance = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    maxDistance = max(BFS(i, j, grid), maxDistance);
                    init();
                }
            }
        }

        return maxDistance <= 0 ? -1 : maxDistance;
    }

    void init()
    {
        for (int i = 0; i < m; ++i)
            fill(used[i].begin(), used[i].end(), -1);
    }

    int BFS(int row, int col, vector<vector<int>>& grid)
    {
        used[row][col] = 0;
        queue<Node> q;
        q.push(Node(row, col));
        while (!q.empty()) {
            Node tmp = q.front(); q.pop();
            if (grid[tmp.x][tmp.y] == 1) return used[tmp.x][tmp.y];

            for (int i = 0; i < 4; ++i) {
                int nextRow = tmp.x + direction[i][0];
                int nextCol = tmp.y + direction[i][1];
                if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n 
                && used[nextRow][nextCol] == -1) {
                    used[nextRow][nextCol] = used[tmp.x][tmp.y] + 1;
                    q.push(Node(nextRow, nextCol));
                }   
            }
        }

        return -1;
    }
};

上面这种方法属于暴力解法，思路是对的，但是在倒数第二个测试用例的时候超时。这道题的问题起始可以转化成，对于每个0，找其和1的最短路，在所有的01最短路中，找最大的值。那么程序也是这么设计的，但是问题也出现在这里，每次都对一个0进行BFS，当数据量很大的时候，肯定会存在很多重复计算，所以需要进行剪枝和优化。

(宽度优先搜索 / BFS) O(nm) 首先将所有 1 位置放入队列，初始化这些位置的距离为 0，其余位置为正无穷。开始宽度优先搜索，每次可以扩展周围的 4 个方向。最后找 0 位置的最大距离。

class Solution {
    int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
public:
    struct Node {
        int x, y;
        Node(int xEle, int yEle) : x(xEle), y(yEle) {}
    };

    int maxDistance(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> path(m, vector<int>(n, INT_MAX));
        queue<Node> q;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    q.push(Node(i, j));
                    path[i][j] = 0;
                }
            }
        }

        while (!q.empty()) {
            Node tmp = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int row = tmp.x + direction[i][0];
                int col = tmp.y + direction[i][1];
                if (0 <= row && row < m && 0 <= col && col < n) {
                    if (path[row][col] > path[tmp.x][tmp.y] + 1) {
                        path[row][col] = path[tmp.x][tmp.y] + 1;
                        q.push(Node(row, col));
                    }
                }
            }
        }

        int res = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && path[i][j] < INT_MAX) {
                    res = max(res, path[i][j]);
                }
            }
        }

        return res;
    }
};