1

行列[n,n]が与えられた場合、[0,0]から[n,n]に非再帰的に到達できる方法の数を調べたいと思います。

私のアプローチは

  1. これまでに移動した行、列、パスを格納するスタクト ​​ノードを作成する
  2. ノードをキューに追加する
  3. 空でなくなるまでキューを繰り返します。行をインクリメントし、列をインクリメントします。キューに追加する
  4. 行=n、列=nの場合はパスを出力します

質問

  1. 行、列、パスを保存する別の方法はありますか
  2. n が非常に大きい場合、キューにノードを格納することが問題になる可能性があります。どうすればこれを回避できますか?

私は再帰的な解決策を探していません。多くのインタビュー フォーラムでこのような質問を目にするので、これが正しいアプローチかどうかを知りたいと思います。

以下はノードの構造と機能です

 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] が与えられた場合、列または行のいずれかを増やすことによって [0,0] から [n,n] に到達できる方法はいくつありますか?

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

下または右にしか移動できない場合 (つまり、行または列を増やす)、二項命題のように見えます。'下' または '右' を '0' または '1' と考えることができます。

nxn マトリックスでは、下/右の条件に従うすべてのパスの長さは n*2-2 になります (たとえば、3x3 の正方形では、パスの長さは常に 4 であり、4x4 の正方形では長さ 6 です)。

x 桁の 2 進数の 0 と 1 の組み合わせの総数は 2^x です。この場合、「x」は n*2-2 ですが、「下」または「右」の数が n-1 を超えることはできないため、すべての組み合わせを使用することはできません。0 と 1 の数が等しいすべてのバイナリの組み合わせが必要なようです。そして解決策は...ただ：

(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 に答える