检查是否有路径经过相同数量的 0 和 1

Submission

运行时间: 36 ms

内存: 17.9 MB

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        if (m + n) % 2 == 0:
            return False 
        
        @cache
        def dfs(i, j, diff): # 从(i, j)出发，以diff的状态，能否达到唯一的（m-1, n-1, 0）状态
            if m + n - 2 - i - j < abs(diff):
                return False 
            if i == m - 1 and j == n - 1:
                return diff == 0 #唯一的True
            if i == m - 1:
                return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1)
            if j == n - 1:
                return dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)
            return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1) or dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)

        ans = dfs(0, 0, 2 * grid[0][0] - 1)
        return ans

Explain

题解的思路基于深度优先搜索（DFS），用于遍历网格并检查是否可以找到一条路径，使得路径上0和1的数量相等。首先，初始化网格的行数m和列数n。若m+n为偶数，则不可能找到这样的路径（因为只有奇数步时，两数可能相等）。使用带缓存的DFS，该缓存有助于减少重复计算。在DFS过程中，使用diff表示当前路径中0和1数量的差值（计算方法为2*当前值-1）。若到达终点时diff为0，则表示0和1数量相等。递归地向右和向下探索，不断更新diff。如果在某个点，所剩步数少于diff的绝对值，则说明不可能平衡0和1，提前结束搜索。

时间复杂度: O(m*n*(m+n))

空间复杂度: O(m*n*(m+n))

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        if (m + n) % 2 == 0:
            return False
        
        @cache
        def dfs(i, j, diff): # 从(i, j)出发，尝试达到(m-1, n-1)位置，diff表示路径上0和1的数量差
            if m + n - 2 - i - j < abs(diff): # 剩余步数小于diff的绝对值，不可能平衡
                return False
            if i == m - 1 and j == n - 1:
                return diff == 0 # 到达终点，检查0和1数量是否平衡
            if i == m - 1:
                return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1) # 只能向右走
            if j == n - 1:
                return dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1) # 只能向下走
            return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1) or dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1) # 向右或向下探索

        ans = dfs(0, 0, 2 * grid[0][0] - 1)
        return ans

Explore

在网格中，从起点到终点走的总步数是固定的，等于m+n-2。如果m+n-2是一个偶数，意味着总步数是奇数。因为一条有效的路径需要在每一步都选择一个格子，所以在奇数步数下，无法使0和1的数量相等（由于你总是以1的数量多1或是0的数量多1结束）。因此，当m+n为偶数时，m+n-2为奇数，不可能在奇数步中让两种数字的数量完全相等。

在网格中，0和1的二值性可以利用数学变换来表达其差异。当遇到1时，计算表达式2*1-1结果为1；遇到0时，2*0-1结果为-1。这种计算方式直接给出了每个格子对0和1数量差的贡献，1增加差异，0减少差异。通过累加这些值，diff有效地跟踪了从路径开始到当前点0和1的净差异，如果diff为0，则说明0和1的数量相等。

缓存用于存储从某个特定位置(i, j)开始，对应特定数量差diff时，是否能找到符合条件的路径的结果。这种方法称为记忆化搜索，它避免了在相同的位置和相同的数量差条件下重复计算DFS的结果，显著提高算法效率，特别是在遇到重复或相似状态时可以直接返回已计算的结果，减少不必要的递归调用。

考虑到每一步只能改变总diff值1（增加1或减少1），剩余步数表示从当前位置到终点的最大可能步数。如果diff的绝对值大于剩余步数，则即使在剩下的每一步都朝着减小diff差异的方向走，也无法使diff达到0。因此，当检测到这种情况时，可以安全地断定当前路径不可能在剩余步数内平衡0和1的数量，从而提前终止搜索，节省计算资源。