网格步行算法code纠错 [英] Grid walking algorithm code correction

查看：226
本文介绍了网格步行算法code纠错的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

网走（50分）： 你是坐落在一个N维网格在位置（X_1，X2，...，x_N）。网格的尺寸（D_1，D_2，...... D_N）。在一个步骤中，您可以在 N 尺寸中的任何一个提前或错后走一步。 （所以总有 2N 可能不同的动作）。有多少种方法可以你把 M 步骤，你不要离开电网在任何时候？你离开的网格，如果你的任何 x_i ，或者 x_i＆LT; = 0或x_i＆GT; D_i 。

输入： 第一行包含测试用例 T 的数量。 T 测试案例可循。对于每个测试的情况下，第一行包含 N 和 M ，第二行包含 X_1 ，X_2 ...，x_N 和第三行中包含 D_1，D_2，......，D_N 。

因此​​，在上述溶液中，我试图把一维数组。 该网站声称 38753340 是答案，但我没有得到它。 

 公共类GridWalking {

    / **
     * @参数ARGS
     * /
    公共静态无效的主要（字串[] args）{

        尝试 {

            长ARR [] =新长[78];
            长POS = 44;
            长卡米尔= 287;

            / *
             *双ARR [] =新的双[3];双POS = 0;双卡米尔= 5;
             * /

            双VAL =计算（ARR，POS，卡米尔）;
            的System.out.println（VAL％1000000007）;

        }赶上（例外五）{
            的System.out.println（E）;
            e.printStackTrace（）;
        }

    }

    公共静态HashMap的＆LT;字符串，双＆GT;计算值=新的HashMap＆LT;字符串，双＆GT;（）;

    私有静态双重计算（长[]改编，长POS，长卡米尔）{

        如果（calculated.containsKey（POS ++卡米尔））{
            返回calculated.get（POS ++卡米尔）;
        }
        如果（0 ==卡米尔）{

            calculated.put（POS ++卡米尔，新的双（1））;
            返回新的双（1）;
        }

        如果（POS == arr.length  -  1）{

            双B =计算（ARR，POS  -  1，卡米尔 -  1）;

            双RET = B;
            calculated.put（POS ++卡米尔，新的双（RET））;
            返回RET;

        }
        如果（POS == 0）{
            双B =计算（ARR，POS + 1，卡米尔 -  1）;

            双RET = B;
            calculated.put（POS ++卡米尔，新的双（RET））;
            返回RET;
        }

        双A =计算（ARR，POS + 1，卡米尔 -  1）;
        双B =计算（ARR，POS  -  1，卡米尔 -  1）;

        双RET =（A + B）;
        calculated.put（POS ++卡米尔，RET）;
        返回RET;
    }

}

解决方案

我已经尝试解决了电网行走问题Hackerrank。这是曾（在ecclipse ATLEAST）在code。但我唐诺，为什么它不给出答案匹配。坚果我想你可以从它那里得到的想法。因为它不使用递归，以执行时间上的问题。

 进口java.io. *;
导入的java.util。*;
导入的java.text *。
导入的java.math *。
导入java.util.regex中*。

公共类解决方案{
    静态诠释计数= 0;
    公共静态无效的主要（字串[] args）抛出FileNotFoundException异常{
        字符串文件名=SRC / testcases.txt; //测试用例只是一个输入包含文件
        档案文件=新的文件（文件名）;
        扫描仪在=新的扫描仪（文件）;
        //in.useDelimiter("[^0-9]+）;
        // ------------------------------------------------ -----------------
        INT T = in.nextInt（）;
        对于（INT T = 0; T＆LT; 1;吨++）{
            INT N = in.nextInt（）;
            INT M = in.nextInt（）;的System.out.println（M =+ M）;
            INT [] X =新INT [N];
            长最大= 1000000007;
            INT [] D =新INT [N];
            对（INT I = 0; I＆所述N; i ++在）x [I] = in.nextInt（）;
            对（INT I = 0; I＆所述N;我+ +）D [I] = in.nextInt（）;
            INT的Dmax = D [0];
            INT DTOTAL = 1;
            对（INT I = 0; I＆所述N;我+ +）如（的Dmax＆所述; D [I]）的Dmax = D [I];
            的for（int i = 0; I＆n种;我++）×[我]  - ;
            对（INT I = 0; I＆所述N;我+ +）DTOTAL * = D [I];字段//总数
            长[] mainarray =新长[DTOTAL]
            长[] mainarraynext =新长[DTOTAL]
            INT [] [] =方式新INT [N] [的Dmax];
            集（X，mainarray，D，1）;
            INT临时[] =新的INT [N];
            为（中间体H = 0; H小于10; H ++）{

                对于（INT J = 0; J＆LT; D​​TOTAL; J ++）{
                    mainarraynext [J] = getsum（逆（J，D），mainarray，D）;
                }
                对于（INT J = 0; J＆LT; D​​TOTAL; J ++）{
                    mainarray [J] = mainarraynext [J]。
                    mainarray [J]％= MAX;
                }
                的System.out.println（Arrays.toString（mainarray））;
            }
            长finalsum = 0;
            对于（INT J = 0; J＆LT; D​​TOTAL; J ++）{
                finalsum + = mainarray [J]。
                //System.out.println(finalsum）;

            }
            的System.out.println（finalsum）;
            //System.out.println(Arrays.toString(inverse(44,D）））;
        }
    }
    公共静态长的get（INT []×长[] mainarray，INT [] D）{
        的for（int i = 0; I＆LT; x.length;我++）{
            如果（X [I]≥= D [I]）返回0;
            如果（X [1]  - ; 0）返回0;
        }
        INT索引= 0;
        的for（int i = 0; I＆LT; D​​.length;我++）{
            指数=（指数* D [I]）+ X [I]
        }
        返回mainarray [指数]
    }
    公共静态INT []逆（INT指数，INT [] D）{
        INT []临时=新的INT [D.length]
        的for（int i = D.length-1; ​​I＆GT; = 0; I  - ）{
            临时[我] =索引％D [I];
            指数=指数/ D [I]
        }
        返回温度;
    }
    公共静态无效套（INT []×长[] mainarray，INT [] D，int值）{
        INT索引= 0;
        的for（int i = 0; I＆LT; D​​.length;我++）{
            指数=（指数* D [I]）+ X [I]
        }
        mainarray [指数] =值;
    }
    公共静态长getsum（INT []×长[] mainarray，INT [] D）{
        INT []临时=新的INT [x.length]
        长总和= 0;
        //为2n个不同的侧面
        对于（INT J = 0; J＆LT; x.length; J ++）{//总和每侧
            温度[J] = X [J]。
        }
        对于（INT J = 0; J＆LT; x.length; J ++）{//总和每侧
            温度[J]  - ;
            总和+ = GET（温度，mainarray，D）;
            温度[J] + = 2;
            总和+ = GET（温度，mainarray，D）;
            温度[J]  - ;
        }
        返回总和;

    }
}

Grid Walking (Score 50 points): You are situated in an N dimensional grid at position (x_1,x2,...,x_N). The dimensions of the grid are (D_1,D_2,...D_N). In one step, you can walk one step ahead or behind in any one of the N dimensions. (So there are always 2N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if you for any x_i, either x_i <= 0 or x_i > D_i.

Input: The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x_1,x_2...,x_N and the 3rd line contains D_1,D_2,...,D_N.

So, in the above solution I'm trying to take one dimensional array. The website claims 38753340 to be the answer, but I'm not getting it. 

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

}

解决方案

I have tried solving that Grid walking problem in Hackerrank. this is the code that had worked(in ecclipse atleast). but i donno why it does not match with given answers. Nut i think you can get the idea from it. Since it does not use recursion, no problem with execution time..

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;

    }
}

这篇关于网格步行算法code纠错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
Java开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆