5

あなたは位置 x,y のグリッドにいます。行の次元は dx,dy です。1 ステップで、行または列で 1 歩前または後ろに歩くことができます。どの時点でもグリッドから離れないように、M ステップを実行できる方法は何通りありますか?
同じ場所に複数回訪問できます。
x,y <= 0 または x,y > dx,dy の場合、グリッドを離れます。
1 <= M <= 300
1 <= x,y <= dx,dy <= 100

入力:
M
xy
dx dy

出力:
方法の数

例:
入力:
1
6 6
12 12

出力:
4

例:
入力:
2
6 6
12 12

出力:
16
位置 6,6 にいる場合、(6,5)、(6,7)、(5,6)、(7,6) まで歩くことができます。

パスカルの三角形を使用してそれを解決する方法に行き詰まっています。それは正しいアプローチですか? 私はすでにブルートフォースを試しましたが、遅すぎます。

C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

T[startpos][stp]
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]
4

3 に答える 3

2

あなたが提供した式で1dの問題を解くことができます。

指定H[pos][step]されたステップ数を使用して水平方向に移動する方法の数を とします。
そしてV[pos][step]、指定されたステップ数を指定して垂直方向に移動する方法の数になります。

水平になるステップの数を繰り返すことができi = 0..M
ます 移動する方法の数 そうですH[x][i]*V[y][M-i]*C[M][i]C は二項係数です。

で H と V をビルドしO(max(dx,dy)*M)、 で 2 番目のステップを実行できO(M)ます。

編集: H と Vの説明。d セルを持つ行があるとします: 1,2,...,d. T[pos][step] = T[pos-1][step-1] + T[pos+1][step-1]前方または後方に移動できるため、セル番号 pos に立っています。

基本ケースはT[0][step] = 0、、、T[d+1][step] = 0ですT[pos][0] = 1。

を想定して H を構築し、 を想定しd = dxて Vを構築しd = dyます。

編集 2:基本的に、アルゴリズムの考え方は、2 次元のいずれかで移動し、チェックも各次元に個別に基づいているため、2 次元の問題を 2 つの 1 次元の問題に分割できます。

于 2012-05-30T09:08:24.357 に答える
0

1つの方法は、O（n ^ 3）動的計画法ソリューションです。

3Dアレイを準備します。

int Z[dx][dy][M]

ここで、Z [i] [j] [n]は、位置（i、j）から始まり、最後のn個が移動するパスの数を保持します。

基本ケースは、すべてのi、jに対してZ [i] [j] [0]=1です。

再帰的な場合は、Z [i] [j] [n + 1] = Z [i-1] [j] [n] + Z [i + 1] [j] [n] + Z [i] [j- 1] [n] + Z [i] [j + 1] [n]（マップ上にある合計に用語のみを含める）

配列が入力されたら、Z [x][y][M]を返します。

スペースを節約するために、使用後にn個の各2D配列を破棄できます。

于 2012-05-30T08:58:45.493 に答える
0

元のhackerrank問題に対して私が構築した Java ソリューションを次に示します。大きなグリッドの場合、永遠に実行されます。おそらく、スマートな数学が必要です。

long compute(int N, int M, int[] positions, int[] dimensions) {
    if (M == 0) {
        return 1;
    }
    long sum = 0;
    for (int i = 0; i < N; i++) {
        if (positions[i] < dimensions[i]) {
            positions[i]++;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]--;
        }
        if (positions[i] > 1) {
            positions[i]--;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]++;
        }
    }
    return sum % 1000000007;
}
于 2016-07-05T20:02:27.073 に答える