雲棲大會限時搶答賽

P1: 和至少為 K 的最短子陣列

Leetcode 862
原題一點沒改。

P2: 滑動拼圖

Leetcode 773
$2\times 3$改成了$3\times 3$。
原本可以直接DFS或者A-start搜尋，但是，現在會T，終止狀態也不好用了。
用優先佇列去維護， 計算和最終狀態的差值，相同step的情況下， 優先選擇差距小的。
可以在優化一些， 排除一些。

import heapq
import collections
class Solution:
    """
    @param init_state: the initial state of chessboard
    @param final_state: the final state of chessboard
    @return: return an integer, denote the number of minimum moving
    """
    def minMoveStep(self, board, target):
        R, C = len(board), len(board[0])
        P = [1] * (R * C)
        for i in range(1, R*C):
            P[i] = 10 * P[i-1]
        f = lambda A: sum(A[i][j] * P[i*C + j] for i in range(R) for j in range(C))
        rs, cs = -1, -1
        for i in range(R):
            for j in range(C):
                if board[i][j] == 0:
                    rs, cs = i, j
        def trans(r, c, state, nr, nc):

            k0 = r * C + c
            k1 = nr * C + nc
            digit = (state // P[k1])% 10
            return state - digit * P[k1] + digit * P[k0]
        

        s_state = f(board)
        f_state = f(target)
        dist_to_f_state = lambda x: abs(x - f_state)
        d = collections.defaultdict(int)
        d[s_state] = 0
        Q = [(0, dist_to_f_state(s_state), rs, cs, s_state)]
        while Q and f_state not in d:
            _, _, r, c, state = heapq.heappop(Q)
            for dx, dy in [[1,0], [-1, 0], [0,1], [0, -1]]:
                nr, nc = r + dx, c + dy
                if 0<= nr < R and 0 <= nc < C:
                    nstate = trans(r, c, state, nr, nc)
                    if nstate not in d or d[nstate] > d[state] + 1:
                        d[nstate] = d[state] + 1
                        heapq.heappush(Q, (d[nstate], dist_to_f_state(nstate),nr, nc, nstate))
        return -1 if f_state not in d else d[f_state]

P3. 地圖跳躍

題目
在正方形的地圖上， 從左上角(0, 0)跳到(n-1, n-1)的所需要的d的最小值。
對於d的定義是： 如果相鄰兩個格子之間的絕對值差值小於等於d，那麼他們可以跳來跳去。
$n\le 1000$, $0\le arr[i]\le 10^5$
解

1. d具有單調性， 如果x滿足，那麼大於x的點也滿足。 而且我們知道答案在$[0,10^5]$中。
2. 二分+驗證。

class Solution:
    def mapJump(self, A):
        n = len(A)
        inf = 10 ** 5
        def canReach(target):
            f = lambda x: x[0] * n + x[1]
            vis = {f([0, 0])}
            Q = [[0,0]]
            while Q:
                x, y = Q[0]
                del Q[0]
                for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and f([nx, ny]) not in vis and abs(A[x][y] - A[nx][ny]) <= target:
                        Q.append([nx, ny])
                        vis.add(f([nx, ny]))
            return f([n-1, n-1]) in vis
        
        L, R = 0, inf
        while L < R:
            mid = (L + R) >> 1
            if canReach(mid):
                L, R = L, mid
            else:
                L, R = mid+1, R
        return R