weekly contest 449。
edge case 放在 hidden case,太壞了。

題目

https://leetcode.com/problems/equal-sum-grid-partition-ii/description/

解法

大致上和 Q2 差不多。
只是改成可以刪除至多一個格子,並且刪除後的所有格子要互相連通。


題目只說到劃分後是非空子矩陣,但沒提到刪除後是否可以為空。

我在這邊想了好久,其實結論很簡單。
格子中的值都是正整數,不管是否允許刪除後為空,都不可能使得空子矩陣和另一半的和相同。
根本不用管。


和 Q2 一樣可以利用對稱性,只討論水平切的情況:

在矩陣長寬至少為 2 的一般情況下,只有兩種情況會在刪除後不連通

  • 上半段只有一列,且刪了非頭尾的元素
  • 下半段只有一列,且刪了非頭尾的元素

換句話說,只要下列滿足任一條件則不影響連通:

  • 子陣列高至少 2
  • 子陣列高為 1,但是刪最左邊最右邊

分類討論三種答案情況:

  • up == down,不用刪
  • up > down,若 (up-down) 存在於上半段,且不破壞連通性
  • up < down,若 (down-up) 存在於下半段,且不破壞連通性

我們只需要在遍歷過程中維護上下半段剩餘的元素即可。


別忘記處理特殊案例 N = 1 。

當原矩陣呈一條直線時,分割後的兩個子矩陣也是直線。
所以兩個子矩陣只能刪除最上面或是最下面的部分,否則會破壞連通性。

示意圖

時間複雜度 O(MN)。
空間複雜度 O(MN)。

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        trans = [list(row) for row in zip(*grid)]
        return solve(grid) or solve(trans)


def solve(a):
    M, N = len(a), len(a[0])

    d2 = Counter()
    down = 0
    for row in a:
        for x in row:
            d2[x] += 1
            down += x

    up = 0
    d = Counter()
    for i in range(M-1):
        for j in range(N):
            x = a[i][j]
            up += x
            d[x] += 1
            down -= x
            d2[x] -= 1

        # 不刪
        if up == down:
            return True

        # 刪上面
        if up > down:
            delta = up - down
            if d[delta] > 0:
                # 特判 M x 1
                if N == 1:
                    if a[0][0] == delta or a[i][0] == delta:
                        return True
                    continue
                if i > 0 or a[0][0] == delta or a[0][-1] == delta:
                    return True

        # 刪下面
        if up < down:
            delta = down - up
            if d2[delta] > 0:
                # 特判 M x 1
                if N == 1:
                    if a[-1][0] == delta or a[i+1][0] == delta:
                        return True
                if i < M-2 or a[-1][0] == delta or a[-1][-1] == delta:
                    return True
    return False

其實不只水平垂直可以複用同一個邏輯,連水平切裡面上下半段也可以複用。
只需要實作檢查上半段的邏輯,將矩陣上下翻轉,就可以刪上下段了。

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        # 1. 水平切
        # 2. 右轉 90 度後水平切 = 垂直切
        trans = [list(row) for row in zip(*grid)]
        return solve(grid) or solve(trans)


def solve(a):
    # 1. 刪上半段
    # 2. 上下翻轉後刪上半段 = 刪下半段
    return delete_up(a) or delete_up(a[::-1])


def delete_up(a):
    M, N = len(a), len(a[0])

    down = 0
    for row in a:
        for x in row:
            down += x

    up = 0
    d = Counter()
    for i in range(M-1):
        for j in range(N):
            x = a[i][j]
            up += x
            d[x] += 1
            down -= x

        # 不刪
        if up == down:
            return True

        # 刪上面
        if up > down:
            delta = up - down
            if d[delta] > 0:
                # 特判 M x 1
                if N == 1:
                    if a[0][0] == delta or a[i][0] == delta:
                        return True
                    continue
                if i > 0 or a[0][0] == delta or a[0][-1] == delta:
                    return True
    return False