リートコード

[LeetCode]チェス盤のナイト確率



Knight Probability Chessboard



NxNチェス盤では、騎士はr番目の行とc番目の列から開始し、正確にK回の移動を試みます。行と列には0のインデックスが付けられているため、左上の正方形は（0、0）であり、右下の正方形は（N-1、N-1）です。

チェスの騎士には、以下に示すように、8つの可能な動きがあります。各動きは、基本方向に2つの正方形、次に直交方向に1つの正方形です。



騎士が移動するたびに、8つの可能な移動の1つをランダムに均一に選択し（駒がチェス盤から外れる場合でも）、そこに移動します。

騎士は、正確にK移動するか、チェス盤から離れるまで移動を続けます。騎士が動きを止めた後もボードに残っている確率を返します。



例：

Input: 3, 2, 0, 0 Output: 0.0625 Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board. From each of those positions, there are also two moves that will keep the knight on the board. The total probability the knight stays on the board is 0.0625.

注意：

  • Nは1から25の間になります。
  • Kは0〜100の間になります。
  • 騎士は常に最初にボードからスタートします。

この質問は、私たちの中国のチェスの馬に相当する、騎士が乗ったNxNのサイズのチェス盤を私たちに与えました。それは「日」という言葉を歩くことができ、私たちに開始位置を与え、そして私たちがKの動きを取ることが許されていると言います。 、Kが移動した後にボードにとどまる確率はどれくらいかを尋ねます。次に、確率を要求するには、最初に分子と分母を別々に見つける必要があります。分子はKが移動した後もボード上にある移動であり、分母は制限のない合計移動です。次に、分母が最適に計算されます。各ステップには8つのジャンプ方法があるため、Kステップは8のK乗になります。重要なのは分子を求めることです。ブロガーは、指定された位置を開始点として開始し、BFSを実行します。各ステップは8つの状況を横断します。チェス盤に遭遇すると、カウンターが1増加し、結果はTLEになります。フォーラムに行ってみんなの解決策を見たところ、全員が別の角度から問題を解決していることがわかりました。騎士の開始位置はあまり気にしませんでしたが、Kがボード上のすべての位置で移動した後にボードに残った移動の合計です。それらすべてを計算し、最後に必要な値を直接返します。前のもので 境界パス外 本質的な違いはありませんが、ベストを交換してもシリーズが失われることはありません。それを行うにはまだDPを使用する必要があります。3次元DPアレイまたは2次元DPアレイを使用できます。ここでは、スペースを節約するために、2次元DPアレイを使用します。ここでdp [i] [ j]は、チェスボード上を意味します（i、j）現在のステップが1に初期化された位置で完了した後、チェスボード上に残った移動の合計。実際には、ステップ次元を時間次元と見なし、更新を続けます。さて、最初に、迷路を横断する4つの方向の座標と同じように、8つの「日」の文字の位置の座標を書き留めましょう。ただし、今回は位置が変更されました。次に、段階的にトラバースします。各ステップでは、ボード上の各位置を完全にトラバースし、dp配列と同じサイズで0に初期化された新しい一時配列tを作成する必要があります。次に、トラバースされたボード上のグリッドごとに、8つのソリューションを実行します。新しい位置がチェス盤上にない場合は、直接スキップします。それ以外の場合は、前の手順でdp配列に対応する値を追加します。チェス盤をトラバースした後、dp配列をこの一時配列tに更新します。以下のコードを参照してください。



解決策1：

クラス解決 { 
public: double knightProbability(int N, int K, int r, int c) { if (K == 0) return 1 vectordouble>> dp(N, vector<double>(N, 1)) vectorint>> dirs{{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}} for (int m = 0 m m) { vectordouble>> t(N, vector<double>(N, 0)) for (int i = 0 i i) { for (int j = 0 j j) { for (auto dir : dirs) x >= N } } dp = t } return dp[r][c] / pow(8, K) } }
また、メモ配列の最適化で再帰を使用して、繰り返しの操作を回避し、OJを渡すこともできます。再帰中のメモ配列は、実際には反復中のdp配列です。ここでは、0に初期化された3次元配列を使用します。再帰関数では、kが0の場合、kステップが実行され、1が返されることを意味します。 memo [k] [r] [c]が0でない場合は、この状況が以前に計算されていることを意味し、直接戻ります。次に、8種類の移動をトラバースし、新しい位置を計算します。チェス盤にない場合はスキップし、memo [k] [r] [c]を更新して、再帰呼び出しの戻り値を新しい位置に追加します。 k-1と新しい位置を入力し、ループを終了した後、memo [k] [r] [c]に戻ります。次のコードを参照してください。

解決策2：

クラス解決 { 
public: vectorint>> dirs{{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}} double knightProbability(int N, int K, int r, int c) { vectordouble>>> memo(K + 1, vectordouble>>(N, vector<double>(N, 0.0))) return helper(memo, N, K, r, c) / pow(8, K) } double helper(vectordouble>>>& memo, int N, int k, int r, int c) { if (k == 0) return 1.0 if (memo[k][r][c] != 0.0) return memo[k][r][c] for (auto dir : dirs) x >= N return memo[k][r][c] } }

参考資料：

https://discuss.leetcode.com/topic/105571/my-accepted-dp-solution

https://discuss.leetcode.com/topic/105597/c-java-dp-concise-solution

この記事はブログガーデンから転送されます グランドヤン のブログ、元のリンク： [LeetCode]チェス盤のナイト確率

、転載が必要な場合は、元のブロガーにご連絡ください。