그리드 워킹 알고리즘 코드 수정

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이 포함됩니다.

따라서 위의 솔루션에서 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; 
    } 

} 

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

를 사용하지 않기 때문에 여기에 내가 원래 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; 
}