algorithm - 矩阵中随频率获得的总特殊值(value)

Question

我有一个 2D 阶矩阵 (M x N)，其中所有单元格都包含 0，除了 K 个包含特殊值的特殊单元格 1。现在我需要从单元格开始说 (0, 0) 并到达单元格(M-1，N-1)。我只能从任何单元格向右或向下移动。现在我需要在 (M-1, N-1) 单元格的每个成功到达中找到我收集了多少个特殊值以及它们的频率是多少？示例:我可以说 3 条路径只包含一个特殊值，我有 10 条路径包含 2 个特殊值......等等。

我需要打印所有可能以相应频率赚取的总特殊值(value)对，即； (2, 10) - 表示有 2 条路径，每条路径的总特殊值均为 10，依此类推。

这似乎是找出从源到目的地的所有 dfs 路径，并计算从源到目的地获得的总特殊值的频率。但它的时间复杂度非常高。

如何最小化时间复杂度或者如果可能的话如何在这里使用动态规划概念？

例子:

0 0 0
0 1 1
0 0 0 

• 这里，有2条路径总特殊值=2，只有1条路径总特殊值=0，3条路径总特殊值=1等。

Answer 1

在这个问题中，通过简单地转换图形就可以很容易地消除可能的路径。

将矩阵转换为有向图，其中每个节点都是一个特殊值。每个节点 (nx , ny)只与其他节点相连(mx , my) , 匹配 nx <= mx && ny <= my && !(nx == mx && ny == my)

    int[][] matrix = getMatrix()
    int specialNumberCount = specialNumberCount()
    int m = getM(), n = getN()

    list points

    for int x in [0 , m[
        for int y in [0 , n[
            if(matrix[x][y] == specialValue())
                points.add(point(x , y));

    int[][] adjacencSpecial = new int[specialNumberCount][specialNumberCount];
    for int i in [0 , length(points)[
        point p = points.get(i)

        for int j in [0 , length(points)[
            if j == i
                continue
            else
                point s = points.get(j)
                if p.x <= s.x AND p.y <= s.y AND (p.x != s.x AND p.y != s.y)
                    adjacencMatrix[i][j] = 1

现在这段代码减少了 M x N 的图的大小至 K .从这一点来看，运行 BFS 应该不会花太长时间。