柵格步行算法代碼校正

Question

柵格步行（得分50分）： 您位於N維柵格位置(x_1,x2,...,x_N)。網格的尺寸是(D_1,D_2,...D_N)。在一個步驟中，您可以在任何一個N維度中前後走一步。 （所以總有2N可能的不同動作）。你有多少種方法可以採取M步驟，以便在任何時候都不會離開電網？如果您有任何x_i，或者x_i <= 0 or x_i > D_i，請離開電網。

輸入： 第一行包含測試用例的數量T。 T測試用例如下。對於每個測試用例，第一行包含N和M，第二行包含x_1,x_2...,x_N，第三行包含D_1,D_2,...,D_N。

因此，在上面的解決方案，我試圖採取一維數組。 該網站聲稱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; 
    } 

} 

Answer 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); 
     } 

    } 

Answer 2

我已經嘗試解決在Hackerrank網格行走問題。這是已經工作的代碼（在ecclipse atleast中）。但我不知道爲什麼它不符合給定的答案。堅果我認爲你可以從中獲得想法。因爲它不使用遞歸，與執行時間沒有問題..

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 
    static int count=0; 
    public static void main(String[] args) throws FileNotFoundException { 
     String filename = "src/testcases.txt";//testcases is just a file containing input 
     File file = new File(filename); 
     Scanner in = new Scanner(file); 
     //in.useDelimiter("[^0-9]+"); 
     //----------------------------------------------------------------- 
     int T=in.nextInt(); 
     for(int t=0;t<1;t++){ 
      int N=in.nextInt(); 
      int M=in.nextInt();System.out.println("M="+M); 
      int[] X=new int[N]; 
      long max=1000000007; 
      int[] D=new int[N]; 
      for(int i=0;i<N;i++) X[i]=in.nextInt(); 
      for(int i=0;i<N;i++) D[i]=in.nextInt(); 
      int Dmax=D[0]; 
      int Dtotal=1; 
      for(int i=0;i<N;i++) if(Dmax<D[i]) Dmax=D[i]; 
      for(int i=0;i<N;i++) X[i]--; 
      for(int i=0;i<N;i++) Dtotal*=D[i];//total number of fields 
      long[] mainarray= new long[Dtotal]; 
      long[] mainarraynext=new long[Dtotal]; 
      int[][] ways=new int[N][Dmax]; 
      set(X, mainarray,D, 1); 
      int temp[]=new int[N]; 
      for(int h=0;h<10;h++){ 

       for(int j=0;j<Dtotal;j++){ 
        mainarraynext[j]=getsum(inverse(j,D),mainarray, D); 
       } 
       for(int j=0;j<Dtotal;j++){ 
        mainarray[j]=mainarraynext[j]; 
        mainarray[j]%=max; 
       } 
       System.out.println(Arrays.toString(mainarray)); 
      } 
      long finalsum=0; 
      for(int j=0;j<Dtotal;j++){ 
       finalsum+=mainarray[j]; 
       //System.out.println(finalsum); 

      } 
      System.out.println(finalsum); 
      //System.out.println(Arrays.toString(inverse(44,D))); 
     } 
    } 
    public static long get(int[] x, long[] mainarray, int[] D){ 
     for(int i=0;i<x.length;i++){ 
      if(x[i]>=D[i]) return 0; 
      if(x[i]<0) return 0; 
     } 
     int index=0; 
     for(int i=0;i<D.length;i++){ 
      index=(index*D[i])+x[i]; 
     } 
     return mainarray[index]; 
    } 
    public static int[] inverse(int index,int[] D){ 
     int[] temp=new int[D.length]; 
     for(int i=D.length-1;i>=0;i--){ 
      temp[i]=index%D[i]; 
      index=index/D[i]; 
     } 
     return temp; 
    } 
    public static void set(int[] x, long[] mainarray, int[] D, int value){ 
     int index=0; 
     for(int i=0;i<D.length;i++){ 
      index=(index*D[i])+x[i]; 
     } 
     mainarray[index]=value; 
    } 
    public static long getsum(int[] x,long[] mainarray, int[] D){ 
     int[] temp=new int[x.length]; 
     long sum=0; 
     //for 2n different sides 
     for(int j=0;j<x.length;j++){//sum in each side 
      temp[j]=x[j]; 
     } 
     for(int j=0;j<x.length;j++){//sum in each side 
      temp[j]--; 
      sum+=get(temp, mainarray, D); 
      temp[j]+=2; 
      sum+=get(temp, mainarray, D); 
      temp[j]--; 
     } 
     return sum; 

    } 
} 

Answer 3

這裏有一個Java解決方案我已經建立了原始hackerrank問題。對於大網格永遠運行。可能需要一些聰明的數學。

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; 
}