纠正网格行走算法

问题描述 投票：0回答：3

网格行走算法：

您位于

N
维度网格中的位置
(x_1,x_2,...,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
。

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

}

因此，在上述解决方案中，我尝试采用一维数组。

该网站声称 

38753340
是答案，但我不明白。

java algorithm data-structures binary-search-tree genetic-algorithm
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);
      }

    }
1
投票

我尝试解决 Hackerrank 中的网格行走问题。这是有效的代码（至少在 eclipse 中）。但我不知道为什么它与给定的答案不匹配。当然，我想你可以从中得到启发。由于它不使用递归，因此执行时间没有问题..

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;

    }
}
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;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.