LC 2850

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        extrasPos, zeroesPos = [], []
        M, N = len(grid), len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j] > 1:
                    extrasPos.append([i, j])
                if grid[i][j] == 0:
                    zeroesPos.append([i, j])
        
        def dfs(i):
            if i == len(zeroesPos):
                return 0
            
            ans = float('inf')
            zx, zy = zeroesPos[i]
            
            for ex, ey in extrasPos:
                if grid[ex][ey] == 1:
                    continue
                
                grid[zx][zy] += 1
                grid[ex][ey] -= 1
                dist = abs(zx - ex) + abs(zy - ey)
                ans = min(ans, dist + dfs(i + 1))
                grid[ex][ey] += 1
                grid[zx][zy] -= 1

            return ans
        
        return dfs(0)