Summary ： Simulation volume Leetcode Summary of questions

1765. The highest point on the map

Give you a size of  m x n  The integer matrix of  isWater , It represents a country made up of land   and waters   A map of cells .

If  isWater[i][j] == 0 , lattice  (i, j)  It's a land   lattice .
If  isWater[i][j] == 1 , lattice  (i, j)  It's a waters   lattice .
You need to arrange the height of each cell according to the following rules ：

The height of each grid must be nonnegative .
If a grid is waters  , Then its height must be 0 .
Any adjacent grid height difference at most   by 1 . When the two squares are due east 、 south 、 In the west 、 North up close to each other , They're called adjacent lattices .（ So they have a common side ）
Find a way to arrange height , Make the highest height value in the matrix   Maximum  .

Please return a size of  m x n  The integer matrix of height , among height[i][j]  It's a grid (i, j)  Height . If there are multiple solutions , Please return   Any one  .

Example 1：

Input ：isWater = [[0,1],[0,0]]
Output ：[[1,0],[2,1]]
explain ： The figure above shows the height of each grid .
The blue grid is the water grid , The green grid is the land grid .
Example 2：

Input ：isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output ：[[1,1,0],[0,1,1],[1,2,2]]
explain ： Of all the arrangements , The maximum feasible height is 2 .
In any arrangement , As long as the highest altitude is 2 In accordance with the above rules , All of them are feasible .

Tips ：

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j]  Or  0 , Or  1 .
There are at least 1  A water grid .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/map-of-highest-peak
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        """  Overtime case：https://leetcode-cn.com/submissions/detail/263359652/testcase/ """
        pass

    @lru_cache(None)
    def next(self,rowid,colid):
        res = []
        for i, j in ((rowid - 1, colid), (rowid, colid - 1), (rowid + 1, colid), (rowid, colid + 1)):
            if 0 <= i < self.height and 0 <= j < self.width and -1==self.res[i][j]:
                res.append([i, j])
        return res

    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        self.isWater = isWater
        self.height,self.width = len(isWater), len(isWater[0])
        self.res = [[w-1 for w in line] for line in isWater]
        q = deque((i,j) for i,line in enumerate(isWater) for j,w in enumerate(line) if w)
        while q:
            i,j = q.popleft()
            for _i,_j in self.next(i,j):
                self.res[_i][_j] = self.res[i][j]+1
                q.append((_i,_j))
        return self.res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.highestPeak(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [[[0,0,1],[1,0,0],[0,0,0]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！