Leetcode 1162. As Far from Land as Possible

[Woodyiiiiiii]

这道题我一开始想着也是直接用DP来做，但显然，递进方程的推导跟增加顺序有关，单单从左上到右下这一顺序是不够的，所以要包括从右下到左上这一个顺序。

class Solution {
    public int maxDistance(int[][] grid) {
        int ans = 0;
        int n = grid.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                } else {
                    if (i - 1 >= 0 && dist[i - 1][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j - 1 >= 0 && dist[i][j - 1] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                } else {
                    if (i + 1 < n && dist[i + 1][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                    }
                    if (j + 1 < n && dist[i][j + 1] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                    }
                }
                ans = Math.max(ans, dist[i][j]);
            }
        }
        return ans == 0 || ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

第二种方法是BFS。

我们从节点为1的位置出发，每次BFS扩散一轮，结果加一，然后要将经历过的节点置1(路径覆盖)，这样最后一轮就是最远的0节点的位置。

class Solution {
    final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int maxDistance(int[][] grid) {
        int ans = 0;
        int n = grid.length;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                int[] cur = q.poll();
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 1) continue;
                    grid[x][y] = 1;
                    q.offer(new int[]{x, y});
                }
            }
            ++ans;
        }
        return ans - 1 <= 0 ? -1 : ans - 1;
    }
}

我尝试过用DFS+记忆化搜索来做，但很难判断回环的情况。

BFS和DFS两种方法，时间复杂度都要尽量保持在O(mnlgmn)以下，同时也要解决环的问题。

看下这题2328. Number of Increasing Paths in a Grid

---

• 1162. As Far from Land as Possible
• Official Solution