python3 解法, 执行用时: 1000 ms, 内存消耗: 42.2 MB, 提交时间: 2022-11-27 12:00:42

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        queue, m, n, cost = [], len(isWater), len(isWater[0]), 0
        for i, row in enumerate(isWater):
            for j, val in enumerate(row):
                # 水域，作为起点入队，并更新为答案需要返回的0
                if val:
                    isWater[i][j] = 0
                    queue.append((i, j))
                # 陆地：先更新为无限大的高度，等BFS时更新它
                else:
                    isWater[i][j] = inf
        while queue:
            nxt = []
            cost += 1
            for i, j in queue:
                for dx, dy in (0, 1), (1, 0), (-1, 0), (0, -1):
                    # 只有没被更新过的陆地才能被更新，否则已经有更近的水域访问过它了
                    if 0 <= (nx := i + dx) < m and 0 <= (ny := j + dy) < n and isWater[nx][ny] > cost:
                        isWater[nx][ny] = cost
                        nxt.append((nx, ny))
            queue = nxt
        return isWater

golang 解法, 执行用时: 272 ms, 内存消耗: 33.4 MB, 提交时间: 2022-11-27 12:00:20

const MAX int = 0x3f3f3f
func highestPeak(isWater [][]int) [][]int {
    m, n, queue, dirs := len(isWater), len(isWater[0]), [][]int{}, [][]int{{1, 0}, {0, 1}, {0, -1}, {-1, 0}}
    for i := 0; i < m; i++{
        for j := 0; j < n; j++{
            if isWater[i][j] == 1{
                isWater[i][j] = 0
                queue = append(queue, []int{i, j})
            } else{
                isWater[i][j] = MAX
            }
        }
    }
    for cost := 1; len(queue) > 0; cost++{
        size := len(queue)
        for i := 0; i < size; i++{
            point := queue[0]
            queue = queue[1:]
            for _, dir := range dirs{
                nx, ny := point[0] + dir[0], point[1] + dir[1]
                if nx >= 0 && ny >= 0 && nx < m && ny < n && isWater[nx][ny] > cost{
                    isWater[nx][ny] = cost
                    queue = append(queue, []int{nx, ny})
                }
            }
        }
    }
    return isWater
}

javascript 解法, 执行用时: 404 ms, 内存消耗: 78.1 MB, 提交时间: 2022-11-27 11:59:52

/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
const DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0]], MAX = 0x3f3f3f
var highestPeak = function(isWater) {
    const m = isWater.length, n = isWater[0].length
    let queue = new Array(), cost = 0
    for(let i = 0; i < m; i++)
        for(let j = 0; j < n; j++)
            if(isWater[i][j] == 1){
                isWater[i][j] = 0
                queue.push([i, j])
            }else{
                isWater[i][j] = MAX
            }
    while(queue.length > 0){
        const nxt = new Array()
        cost++
        for(const point of queue)
            for(const dir of DIRS){
                const nx = point[0] + dir[0], ny = point[1] + dir[1]
                if(nx >= 0 && ny >= 0 && nx < m && ny < n && isWater[nx][ny] > cost){
                    isWater[nx][ny] = cost
                    nxt.push([nx, ny])
                }
            }
        queue = nxt
    }
    return isWater
};

golang 解法, 执行用时: 228 ms, 内存消耗: 51.2 MB, 提交时间: 2022-11-27 11:59:11

type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func highestPeak(isWater [][]int) [][]int {
    m, n := len(isWater), len(isWater[0])
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
        for j := range ans[i] {
            ans[i][j] = -1 // -1 表示该格子尚未被访问过
        }
    }
    q := []pair{}
    for i, row := range isWater {
        for j, water := range row {
            if water == 1 { // 将所有水域入队
                ans[i][j] = 0
                q = append(q, pair{i, j})
            }
        }
    }
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, d := range dirs {
            if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && ans[x][y] == -1 {
                ans[x][y] = ans[p.x][p.y] + 1
                q = append(q, pair{x, y})
            }
        }
    }
    return ans
}

python3 解法, 执行用时: 1268 ms, 内存消耗: 77.9 MB, 提交时间: 2022-11-27 11:58:41

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[water - 1 for water in row] for row in isWater]
        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)  # 将所有水域入队
        while q:
            i, j = q.popleft()
            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
                    ans[x][y] = ans[i][j] + 1
                    q.append((x, y))
        return ans