算法搜索

将问题转化为枚举全排列的问题

字数统计: 1.1k字   |   阅读时长: 4分
,

摘要: 问题转化：将问题转化为枚举全排列

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个看似简单的题，但还是有一个小难点就是能够想到这是一个枚举全排列的问题。这需要进行一些问题转化的思路，发现所有可能的走法与需要移动的石头的全排列一一对应。

经过问题转化后，通过常规的搜索/回溯来枚举全排列即可解决问题。

本题也是一个非常典型的费用流问题，以后有时间我们再来探讨。

题目

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

提示：

1
2
3
grid.length == grid[i].length == 3
0 <= grid[i][j] <= 9
grid 中元素之和为 9 。

示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。
总共需要 4 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 4 。

题解

算法: 问题转化，枚举全排列

对于 $grid[i][j]$，如果该位置的石头数量为 0，则需要将一个其他位置的石头移入到这里，将其记录到一个数组 target_list。

如果该位置的石头数量大于 1，则该位置需要移出 $grid[i][j] - 1$ 个石头，将其记录到 source_list。

最终 source_list 中的每个石头，最终都需要到达 target_list 中的某个石头。并且这个对应关系是一一对应的。因此 source_list 的一个全排列就对应了一种走法。

枚举 source_list 的全排列，然后计算其对应走法的移动次数，取最小值即可。

代码 (Python)

使用 常见的枚举方式 中通过递归实现有重复元素集合的排列的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def dist(s: int, t: int) -> int:
    return abs(s[0] - t[0]) + abs(s[1] - t[1])

INF = int(1e9)

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        def dfs(i: int) -> None:
            nonlocal s
            nonlocal ans
            if i == n:
                ans = min(ans, s)

            for j in range(n):
                if j in setting:
                    continue
                setting.add(j)
                s += dist(source_list[j], target_list[i])
                dfs(i + 1)
                s -= dist(source_list[j], target_list[i])
                setting.remove(j)

        source_list = []
        target_list = []
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    target_list.append((i, j))
                elif grid[i][j] > 1:
                    source_list.extend([(i, j)] * (grid[i][j] - 1))

        n = len(source_list)
        if n == 0:
            return 0

        ans = INF
        s = 0
        setting = set()
        dfs(0)

        return ans

代码 (Python)

使用 itertools 中的 permutations 组件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from itertools import permutations

def dist(s: int, t: int) -> int:
    return abs(s[0] - t[0]) + abs(s[1] - t[1])

INF = int(1e9)

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        source_list = []
        target_list = []
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    target_list.append((i, j))
                elif grid[i][j] > 1:
                    source_list.extend([(i, j)] * (grid[i][j] - 1))

        n = len(source_list)
        if n == 0:
            return 0

        ans = INF
        for source_perm in permutations(source_list):
            s = 0
            for x, y in zip(source_perm, target_list):
                s += dist(x, y)
            ans = min(ans, s)

        return ans
Share