网格步行算法代码校正
网格散步 （得分50分）：您位于位置(x_1,x2,...,x_N)的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;
}
}
您需要更改关键值，如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);
}
}
我已经尝试在Hackerrank中解决Grid问题。 这是已经工作的代码（在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;
}
}
这是我为最初的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;
}