1

给定一个矩阵 [n,n] 我想找出我们可以从 [0,0] 到 [n,n] 非递归地达到多少种方式。

我的方法是

  1. 创建一个结构节点来存储到目前为止行进的行、列和路径
  2. 将节点添加到队列
  3. 遍历队列直到不为空。增加行，增加列。添加到队列
  4. 如果 row=n, col=n 则打印路径

问题

  1. 是否有不同的方式来存储行、列和路径
  2. 如果 n 非常大，将节点存储在 Queue 中可能会出现问题。我们怎样才能避免这种情况？

请不要我不是在寻找递归解决方案。我在许多面试论坛上看到这样的问题，所以想知道这是否是正确的方法。

下面是Node的结构和功能

 struct Node
    {
        public int row;
        public int col;
        public string path;

        public Node(int r, int c, string p)
        {
            this.row = r;
            this.col = c;
            this.path = p;
        }
    }




 public static void NextMoveNonRecursive(int max)
    {

        int rowPos;
        int colPos;
        string prevPath = "";
        Node next;

        while (qu.Count > 0)
        {
            Node current = qu.Dequeue();
            rowPos = current.row;
            colPos = current.col;
            prevPath = current.path;

            if (rowPos + 1 == max && colPos + 1 == max)
            {
                Console.WriteLine("Path = ..." + prevPath);
                TotalPathCounter++;
            }

            if (rowPos + 1 < max)
            {
                if (prevPath == "")
                    prevPath = current.path;

                prevPath = prevPath + ">" + (rowPos + 1) + "" + (colPos);
                next = new Node(rowPos + 1, colPos, prevPath);
                qu.Enqueue(next);
                prevPath = "";
            }

            if (colPos + 1 < max)
            {

                if (prevPath == "")
                    prevPath = current.path;

                prevPath = prevPath + ">" + (rowPos) + "" + (colPos+1);
                next = new Node(rowPos, colPos+1, prevPath);
                qu.Enqueue(next);
                prevPath = "";
            }

        }
    }
4

3 回答 3

3

让dp[i, j]是从[0, 0]到的路径数[i, j]。

我们有：

dp[0, i] = dp[i, 0] = 1 for all i = 0 to n
dp[i, j] = dp[i - 1, j] +     come down from all paths to [i - 1, j]
           dp[i, j - 1] +     come down from all paths to [i, j - 1]         
           dp[i - 1, j - 1]   come down from all paths to [i - 1, j - 1] 
           for i, j > 0

dp[i - 1, j - 1]如果不能同时增加行和列，请从上述总和中删除。

dp[n, n]会有你的答案。

于 2013-02-16T21:55:41.220 回答
1

给定一个矩阵 [n,n]，通过增加 col 或 row 可以从 [0,0] 到 [n,n] 有多少种方式？

(n*2-2) choose (n*2-2)/2

如果只能向下或向右（即增加行或列），这似乎是一个二元命题——我们可以将“向下”或“向右”视为“0”或“1”。

在 nxn 矩阵中，遵循向下/向右条件的每条路径的长度均为 n*2-2（例如，在 3x3 正方形中，路径的长度始终为 4；在 4x4 正方形中，长度为 6）。

x 位二进制数中 0 和 1 的总组合数为 2^x。在这种情况下，我们的 'x' 是 n*2-2，但我们不能使用所有组合，因为 'down' 或 'right' 的数量不能超过 n-1。看来我们需要所有具有相同数量的 0 和 1 的二进制组合。解决方案是...... tada：

(n*2-2) choose (n*2-2)/2

在 Haskell 中，您可以编写以下非递归函数来列出路径：

import Data.List
mazeWays n = nub $ permutations $ concat $ replicate ((n*2-2) `div` 2) "DR"

如果你想要路径的数量，那么：

length $ mazeWays n
于 2013-02-17T02:13:50.207 回答
0

带有示例的 Javascript 解决方案

var arr = [
    [1, 1, 1, 0, 0, 1, 0],
    [1, 0, 1, 1, 1, 1, 0],
    [1, 0, 1, 0, 1, 0, 0],
    [1, 1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1]
];

function sols2(arr){
    var h = arr.length,
            w = arr[0].length,
            i, j, current, left, top;

    for(i = 0; i < h; i++){
        for(j = 0; j < w; j++){
            current = arr[i][j];
            top = i === 0 ? 0.5 : arr[i - 1][j];
            left = j === 0 ? 0.5 : arr[i][j-1];

            if(left === 0 && top === 0){
                arr[i][j] = 0;
            } else if(current > 0 && (left > 0 || top > 0)){
                arr[i][j] = (left + top) | 0;
            } else {
                console.log('a6');
                arr[i][j] = 0;
            }       
        }
    }
    return arr[h-1][w-1];
}

sols2(arr);
于 2014-02-25T04:24:38.927 回答