2850.将石头分散到网格图的最少移动次数

链接：2850.将石头分散到网格图的最少移动次数
难度：Medium
标签：广度优先搜索、数组、动态规划、矩阵
简介：请你返回每个格子恰好有一个石头的 最少移动次数 。

题解 1 - python

• 编辑时间：2024-07-21
• 执行用时：56ms
• 内存消耗：16.36MB
• 编程语言：python
• 解法介绍：暴力枚举。

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        arr1 = [(i, j, grid[i][j]) for i in range(3) for j in range(3) if grid[i][j] > 1]
        arr0 = [(i, j) for i in range(3) for j in range(3) if grid[i][j] == 0]
        self.res = inf
        def dfs(i0: int, cur: int = 0) -> int:
            if i0 == len(arr0): self.res = min(self.res, cur)
            else:
                for i1 in range(len(arr1)):
                    old_item = arr1[i1]
                    if old_item[2] > 1:
                        arr1[i1] = (old_item[0], old_item[1], old_item[2] - 1)
                        dfs(i0 + 1, cur + abs(old_item[0] - arr0[i0][0]) + abs(old_item[1] - arr0[i0][1]))
                        arr1[i1] = old_item
        dfs(0)
        return self.res