尽可能远离陆地

Question

我正在处理Leetcode中的一个问题“尽可能远离陆地”，可以在这里找到：https://leetcode.com/problems/as-far-from-land-as-possible/

一个保证有效的解决方案是有4个DP阵列，每个阵列从网格的不同角开始，当你到达另一个角时，计算到最近陆地的距离。最后，取所有4个数组中元素的最小值，就可以得到正确的解。你知道吗

我试着写一个DP解决方案，它只尝试做一个数组，通过四个方向计算每个数组。你知道吗

我的代码给出了错误的答案，我似乎找不到错误所在。你知道吗

def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dpfin = [[float('inf') for k in range(N)] for m in range(N)]

        for k in range(N):
            for m in range(N):
                origk = k
                if grid[k][m] == 1:
                    dpfin[k][m] = 0                    
                elif k == 0 and m == 0:
                    pass
                elif k == 0:
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k][m-1] + 1)
                    k = N - 1 - k
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k][m-1] + 1)
                    m = N - 1 - m
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k][m-1] + 1)
                    k = origk
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k][m-1] + 1)
                elif m == 0:
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k-1][m] + 1)
                    k = N - 1 - k
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k-1][m] + 1)
                    m = N - 1 - m
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k-1][m] + 1)
                    k = origk
                    dpfin[k][m] = min(dpfin[k][m], dpfin[k-1][m] + 1)
                else:
                    dpfin[k][m] = min( min(dpfin[k-1][m],dpfin[k][m-1])+1,dpfin[k][m])
                    k = N - 1 - k
                    dpfin[k][m] = min( min(dpfin[k-1][m],dpfin[k][m-1])+1,dpfin[k][m])
                    m = N - 1 - m
                    dpfin[k][m] = min( min(dpfin[k-1][m],dpfin[k][m-1])+1,dpfin[k][m])
                    k = origk
                    dpfin[k][m] = min( min(dpfin[k-1][m],dpfin[k][m-1])+1,dpfin[k][m])

        maxi = 0
        for k in range(N):
            for m in range(N):
                maxi = max(maxi,dpfin[k][m])
        if maxi == float('inf') or maxi == 0:
            return -1
        return maxi

Answer 1

我不得不承认这很难，但我想我有了第一个“未优化”的解决方案。首先是代码，然后是解释：

class Solution:
    def _rec_fixDP(self, grid, DP, r, c, max_offset, dist):
        if r < 0 or c < 0 or r > max_offset or c > max_offset:
            return

        if grid[r][c] != 1 and (DP[r][c] == -1 or DP[r][c] > dist):
            DP[r][c] = dist
            self._rec_fixDP(grid, DP, r - 1, c, max_offset, dist + 1)
            self._rec_fixDP(grid, DP, r, c - 1, max_offset, dist + 1)
            self._rec_fixDP(grid, DP, r + 1, c, max_offset, dist + 1)
            self._rec_fixDP(grid, DP, r, c + 1, max_offset, dist + 1)

    def _dp_iteration(self, r, c, grid, DP):
        if grid[r][c] == 0:
            dp_left = -1 if r - 1 < 0 else DP[r - 1][c]
            dp_up = -1 if c - 1 < 0 else DP[r][c - 1]

            if dp_left == -1 and dp_up == -1:
                DP[r][c] = -1
            elif dp_left == -1 and dp_up != -1:
                DP[r][c] = dp_up + 1
            elif dp_left != -1 and dp_up == -1:
                DP[r][c] = dp_left + 1
            else:
                DP[r][c] = min(dp_left, dp_up) + 1
        else:
            DP[r][c] = 0
            max_offset = max(r, c)

            self._rec_fixDP(grid, DP, r - 1, c, max_offset, 1)
            self._rec_fixDP(grid, DP, r, c - 1, max_offset, 1)



    def maxDistance(self, grid) -> int:
        n = len(grid)
        DP = [[-1 for i in range(n)] for m in range(n)]

        for i in range(n):
            r = i
            for c in range(i):
                self._dp_iteration(r, c, grid, DP)

            c = i
            for r in range(i + 1):
                self._dp_iteration(r, c, grid, DP)

        cur_max = -1
        for i in DP:
            cur_max = max(cur_max, max(i))

        print(DP)

        return cur_max if cur_max > 0 else -1

sol = Solution()
l = [[0,0,0],[0,0,0],[0,0,1]]
print(sol.maxDistance(l))

我已经把它交给leetcode.com结果如下：

Runtime: 860 ms, faster than 19.20% of Python3 online submissions for As Far from Land as Possible.

Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for As Far from Land as Possible.

---

考虑一下这个简单的网格

1    2    3
4    5    6
7    8    9

我以这种方式在grid上循环：1 4 2 5 7 8 3 6 9。这是因为当我访问grid[r][c]时，我已经访问了grid[r - 1][c]和grid[r][c - 1]。你知道吗

接下来，逻辑被分成两部分：whengrid[r][c] = 0和whengrid[r][c] = 1。你知道吗

当网格[r][c]=0时

DP[r][c] = min(DP[r - 1][c], DP[r][c - 1]) + 1

The exception is the value -1: it means it has not been found a land cell yet.

当网格[r][c]=1时

DP[r][c] = 0

Even if this part is pretty simple (the distance between the land cell and itself is 0), you also need to fix all the previous calculated distances, since they could all be -1 or they could have large values. This last part is executed by _rec_fixDP, called until the current distance is lesser than the stored one.

复杂性很容易估计：您需要在所有单元格上循环至少一个单元格（在最佳情况下是一个），但是_rec_fixDP可以重新访问以前的所有单元格。所以：

最佳情况：O(n^2)

平均情况：O(n^4)

不过，我怀疑在不到O(n^4)的时间内就可以做到这一点。你知道吗