0

グリッド ウォーキング(スコア 50 ポイント): あなたは N 次元グリッドの位置 にい(x_1,x2,...,x_N)ます。グリッドの寸法は(D_1,D_2,...D_N)です。1 つのステップで、どのN次元でも 1 歩進んだり後ろに歩いたりできます。（したがって、常に2N異なる動きが可能です）。Mどの時点でもグリッドから離れないように、何通りの方法でステップを踏むことができますか? x_iいずれかの場合は、グリッドを離れますx_i <= 0 or x_i > D_i。

入力: 最初の行には、テスト ケースの数が含まれますT。Tテストケースが続きます。各テスト ケースについて、最初の行には and が含まNれM、2 行目には が含まれx_1,x_2...,x_N、3 行目には が含まれますD_1,D_2,...,D_N。

したがって、上記のソリューションでは、1 次元配列を取得しようとしています。ウェブサイトは答えであると主張38753340していますが、私はそれを得ていません.

public class GridWalking {

    /**
     * @param args
     */
    public static void main(String[] args) {

        try {

            long arr[] = new long[78];
            long pos = 44;
            long totake = 287;

            /*
             * Double arr[] = new Double[3]; Double pos = 0; Double totake = 5;
             */

            Double val = calculate(arr, pos, totake);
            System.out.println(val % 1000000007);

        } catch (Exception e) {
            System.out.println(e);
            e.printStackTrace();
        }

    }

    public static HashMap<String, Double> calculated = new HashMap<String, Double>();

    private static Double calculate(long[] arr, long pos, long totake) {

        if (calculated.containsKey(pos + "" + totake)) {
            return calculated.get(pos + "" + totake);
        }
        if (0 == totake) {

            calculated.put(pos + "" + totake, new Double(1));
            return new Double(1);
        }

        if (pos == arr.length - 1) {

            Double b = calculate(arr, pos - 1, totake - 1);

            Double ret = b;
            calculated.put(pos + "" + totake, new Double(ret));
            return ret;

        }
        if (pos == 0) {
            Double b = calculate(arr, pos + 1, totake - 1);

            Double ret = b;
            calculated.put(pos + "" + totake, new Double(ret));
            return ret;
        }

        Double a = calculate(arr, pos + 1, totake - 1);
        Double b = calculate(arr, pos - 1, totake - 1);

        Double ret = (a + b);
        calculated.put(pos + "" + totake, ret);
        return ret;
    }

}
4

3 に答える 3

1

のようにキー値を変更する必要がありますpos + "_" + totake。

私はそれを書き直しましたが、動作するかどうかはわかりません。完了するまでに時間がかかりすぎます。

    public class GridWalking {

      static long arr_length = 78;
      static long pos = 44;
      static long totake = 287;
      static long count = 0;

      /**
       * @param args
       */
      public static void main(String[] args) {
        try {
          calculate(pos, totake);
          System.out.println(count % 1000000007);
        } catch (Exception e) {
          System.out.println(e);
          e.printStackTrace();
        }
      }

      private static void calculate(long pos, long totake) {
        if (pos < 0 || pos > arr_length - 1)
          return;

        if (0 == totake) {
          count++;
          return;
        }

        calculate(pos + 1, totake - 1);
        calculate(pos - 1, totake - 1);
      }

    }
于 2012-08-12T11:15:44.360 に答える
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:03:59.713 に答える