In this Post, we will solve HackerRank Grid Walking Problem Solution.
You are situated in an n dimensional grid at position (x[1], [2], …, [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. This implies that there are always 2 x n possible moves if movements are unconstrained by grid boundaries. How many ways can you take m steps without leaving the grid at any point? You leave the grid if at any point [i], either [i] < 0 or x[i]> D[i].
For example, you start off in a 3 dimensional grid at position = [2, 2, 2]. The dimensions of the grid are D = [3, 3, 3], so each of your axes will be numbered from 1 to 3. If you want to move m = 1 step, you can move to the following coordinates: {[1, 2, 2], [2, 1, 2], [2, 2, 1], [3, 2, 2], [2, 3, 2], [2, 2, 3]}.
If we started at x = [1, 1, 1] in the same grid, our new paths would lead to {[1, 1, 2], [1, 2, 1], [2, 1, 1]}. Other moves are constrained by a[i] 0.
Function Description
Complete the gridWalking function in the editor below. It should return an integer that represents the number of possible moves, modulo (109 + 7). gridWalking has the following parameter(s):
m: an integer that represents the number of steps
Input Format
The first line contains an integer t, the number of test cases.
Each of the next t sets of lines is as follows:
- The first line contains two space-separated integers, n and m
- The next line contains n space-separated integers a[i].
- The third line of each test contains n space-separated integers D[i].
Sample Input
1
2 3
1 1
2 3
Sample Output
12

Grid Walking C Solution
#include<stdio.h>
#include<stdlib.h>
//using namespace std;
typedef long long int ll;
ll invr(ll x) {
ll M=1000000007;
ll a = 1, b = x;
while (b != 1) {
ll c = M / b;
a *= c; a %= M;
b *= c; b %= M;
if (b > M/2) { a = M - a; b = M - b; }
}
return a;
}
int main(){
ll cases,ww,i,j,k,l,m,n;
ll *** a;
a=(ll ***)malloc(11*sizeof(ll **));
for(i=0;i<11;i++){
a[i]=(ll **)malloc(101*sizeof(ll *));
for(j=0;j<101;j++){
a[i][j]=(ll *)malloc(301*sizeof(ll));
}
}
ll ** b;
b=(ll **)malloc(301*sizeof(ll *));
for(i=0;i<301;i++){
b[i]=(ll *)malloc(11*sizeof(ll));
}
ll *x;
x=(ll *)malloc(11*sizeof(ll));
ll *d;
d=(ll *)malloc(11*sizeof(ll));
ll * fact;
fact=(ll *)malloc(301*sizeof(ll));
ll * inv;
inv=(ll *)malloc(301*sizeof(ll));
fact[1]=1;
for(i=2;i<=300;i++){
fact[i]=(i*fact[i-1])%1000000007;
}
for(i=1;i<=300;i++){
inv[i]=invr(fact[i]);
}
scanf("%lld",&cases);
for(ww=0;ww<cases;ww++){
scanf("%lld",&n);
scanf("%lld",&m);
for(i=1;i<=n;i++){
scanf("%lld",&x[i]);
}
for(i=1;i<=n;i++){
scanf("%lld",&d[i]);
}
for(i=1;i<=n;i++){
for(j=1;j<=d[i];j++){
if(j==1 || j==d[i]){
if(d[i]==1)a[i][j][1]=0;
else a[i][j][1]=1;
}
else{
a[i][j][1]=2;
}
}
}
for(k=2;k<=m;k++){
for(i=1;i<=n;i++){
for(j=1;j<=d[i];j++){
if(j==1){
if(d[i]==1)a[i][j][k]=0;
else a[i][j][k]=a[i][2][k-1];
}
else if(j==d[i]){
a[i][j][k]=a[i][j-1][k-1];
}
else{
a[i][j][k]=(a[i][j-1][k-1]+a[i][j+1][k-1])%1000000007;
}
}
}
}
//printf("hello\n");
for(k=1;k<=m;k++){
for(i=1;i<=n;i++){//printf("hello\n");
if(k==1){
if(i==1){
b[k][i]=a[1][x[1]][1];
}
else{
b[k][i]=(a[i][x[i]][1]+b[k][i-1])%1000000007;
}
}
else{
if(i==1){
b[k][i]=a[1][x[1]][k];
}
else{
int s;
s=x[i];
b[k][i]=(a[i][s][k]+b[k][i-1])%1000000007;
//if(k==5 && i==2)break;
for(l=1;l<k;l++){
b[k][i]=(b[k][i]+((a[i][s][l]*((b[k-l][i-1]*((fact[k]*((inv[l]*inv[k-l])%1000000007))%1000000007))%1000000007))%1000000007))%1000000007;
/*if(k==5 && i==2 && l==2){
printf("%lld\n",fact[k]);
printf("%lld\n",fact[k]*((inv[l]*inv[k-l])%1000000007));
printf("%lld\n",inv[k-l]);
printf("%lld\n",(fact[k]*(inv[l]*inv[k-l])%1000000007)%1000000007);
//break;
}*/
}
}
}
}
}
//printf("hello\n");
/*for(i=1;i<=8;i++){
for(j=1;j<=2;j++){
printf("%lld ",b[i][j]);
}
printf("\n");
}*/
printf("%lld\n",b[m][n]);
}
//printf("%lld",(6*(ll)inv[2])%1000000007);
return 0;
}
Grid Walking C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
//#include <unordered_map>
using namespace std;
typedef long long int ll;
const int max_N = 11, max_S = 101, max_M = 301;
const ll modulo = 1000*1000*1000+7;
ll D[max_N+1], X[max_N+1];
int n, m;
ll CC[max_M][max_M];
ll C(int n, int k) {
if (n<k) return 0LL;
if (CC[n][k] == 0) {
if (n == 0 || k == 0)
CC[n][k] = 1LL;
else
CC[n][k] = (C(n-1, k-1) + C(n-1, k)) % modulo;
}
return CC[n][k];
}
vector<ll> count_dimension(int d, int m) {
vector<ll> p(D[d], 0LL);
vector<ll> upd(D[d], 0LL);
vector<ll> res(m+1, 0LL);
res[0] = 1;
p[X[d]] = 1;
for(int steps=1; steps<=m; ++steps) {
for(int i=1; i<D[d]-1; ++i)
upd[i] = (p[i-1]+p[i+1]) % modulo;
upd[0] = (D[d] > 1) ? p[1] : 0;
upd[D[d]-1] = (D[d] > 1) ? p[D[d]-2] : 0;
for(int i=0; i<D[d]; ++i) {
res[steps] = (res[steps] + upd[i]) % modulo;
p[i] = upd[i];
}
//res[steps] = (1LL * res[steps] * C(m, steps)) % modulo;
}
return res;
}
int main() {
//cout << C(3,2) << endl;
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for(int i=0; i<n; ++i) {
cin >> X[i];
X[i]--;
}
for(int i=0; i<n; ++i) {
cin >> D[i];
//D[i]--;
}
vector<vector<ll>> pathes(n);
for(int i=0; i<n; ++i) {
pathes[i] = std::move(count_dimension(i, m));
//for(int j=0; j<=m; ++j)
// cout << pathes[i][j] << ' ';
//cout << endl;
}
vector<ll> A(pathes[0]);
vector<ll> next_A(m+1);
next_A[0] = 1;
for(int i=1; i<n; ++i) {
for(int j=1; j<=m; ++j) {
ll v = 0;
for(int k=0; k<=j; ++k)
v = (v + (C(j, k)*((A[k]*pathes[i][j-k] % modulo)) % modulo) ) % modulo;
next_A[j] = v;
}
for(int j=0; j<=m; ++j)
A[j] = next_A[j];
}
cout << A[m] << endl;
}
return 0;
}
Grid Walking C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
public static int GridWalking(int numSteps, List<int> coords, List<int> dims)
{
var m = 1000000007;
var numWaysPerDim = new long[dims.Count, numSteps + 1];
for (var i = 0; i < dims.Count; ++i) {
var numWays = new long[dims[i], numSteps + 1];
numWays[coords[i] - 1, 0] = 1;
numWaysPerDim[i, 0] = 1;
for (var j = 1; j <= numSteps; ++j) {
for (var k = 0; k < dims[i]; ++k) {
numWays[k, j] = (
(k - 1 >= 0 ? numWays[k - 1, j - 1] : 0) +
(k + 1 < dims[i] ? numWays[k + 1, j - 1] : 0)
) % m;
numWaysPerDim[i, j] = (numWaysPerDim[i, j] + numWays[k, j]) % m;
}
}
}
var coefs = CalculateBinomialCoefficients(numSteps, m);
var numWaysCombined = new long[dims.Count, numSteps + 1];
for (var i = 0; i <= numSteps; ++i) {
numWaysCombined[0, i] = numWaysPerDim[0, i];
}
for (var i = 1; i < dims.Count; ++i) {
for (var j = 0; j <= numSteps; ++j) {
for (var k = 0; k <= j; ++k) {
numWaysCombined[i, j] = (numWaysCombined[i, j] +
((((numWaysCombined[i - 1, k] * numWaysPerDim[i, j - k]) % m) * coefs[j, k]) % m)) % m;
}
}
}
return (int)numWaysCombined[dims.Count - 1, numSteps];
}
private static long[,] CalculateBinomialCoefficients(long n, long m) {
var coefs = new long[n + 1, n + 1];
coefs[0, 0] = 1;
for (var i = 1; i <= n; ++i) {
coefs[i, 0] = 1;
for (var j = 1; j < n; ++j) {
coefs[i, j] = (coefs[i - 1, j - 1] + coefs[i - 1, j]) % m;
}
coefs[i, n] = 1;
}
return coefs;
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int t = Convert.ToInt32(Console.ReadLine().Trim());
for (int tItr = 0; tItr < t; tItr++)
{
string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
int n = Convert.ToInt32(firstMultipleInput[0]);
int m = Convert.ToInt32(firstMultipleInput[1]);
List<int> x = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(xTemp => Convert.ToInt32(xTemp)).ToList();
List<int> D = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(DTemp => Convert.ToInt32(DTemp)).ToList();
int result = Result.GridWalking(m, x, D);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}
Grid Walking Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the gridWalking function below.
*/
static long[][] c;
static void initBinomials(long mod, int m) {
c = new long[m + 1][m + 1];
c[0][0] = 1;
for (int i = 0; i <= m; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
}
public static long[] ways(long mod, int x, int d, int m) {
long[] w = new long[m + 1];
long[] p = new long[d];
p[x - 1] = 1;
w[0] = 1;
for (int t = 1; t <= m; t++) {
long[] p1 = new long[d];
for (int i = 0; i < p1.length; i++) {
if (i > 0) p1[i] = (p1[i] + p[i - 1]) % mod;
if (i + 1 < d) p1[i] = (p1[i] + p[i + 1]) % mod;
}
p = p1;
for (int i = 0; i < d; i++) w[t] = (w[t] + p[i]) % mod;
}
return w;
}
static long[] apply(long mod, long[] W, long[] w) {
long[] R = new long[W.length];
for (int i = 0; i < W.length; i++) {
for (int j = 0; i + j < W.length; j++) {
long p = (w[i] * W[j]) % mod;
R[i + j] = (R[i + j] + p * c[i + j][i]) % mod;
}
}
return R;
}
static int gridWalking(int m, int[] x, int[] D) {
long mod = 1000_000_007;
initBinomials(mod, m);
long[] W = ways(mod, x[0], D[0], m);
for (int i = 1; i < D.length; i++) {
long[] w = ways(mod, x[i], D[i], m);
W = apply(mod, W, w);
}
return (int)W[m];
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(scanner.nextLine().trim());
for (int tItr = 0; tItr < t; tItr++) {
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0].trim());
int m = Integer.parseInt(nm[1].trim());
int[] x = new int[n];
String[] xItems = scanner.nextLine().split(" ");
for (int xItr = 0; xItr < n; xItr++) {
int xItem = Integer.parseInt(xItems[xItr].trim());
x[xItr] = xItem;
}
int[] D = new int[n];
String[] DItems = scanner.nextLine().split(" ");
for (int DItr = 0; DItr < n; DItr++) {
int DItem = Integer.parseInt(DItems[DItr].trim());
D[DItr] = DItem;
}
int result = gridWalking(m, x, D);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
}
}
Grid Walking JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
function gridWalking(m, x, D) {
const MOD = BigInt(1e9 + 7);
const add = (a, b) => (BigInt(a) + BigInt(b)) % MOD;
const mul = (a, b, c = 1) => (((BigInt(a) * BigInt(b)) % MOD) * BigInt(c)) % MOD;
const binom = new Array(m + 1);
for (let i = 0; i <= m; i += 1) {
binom[i] = new Array(m + 1).fill(0);
binom[i][0] = 1;
binom[i][i] = 1;
for (let j = 1; j < i; j += 1) {
binom[i][j] = add(binom[i - 1][j - 1], binom[i - 1][j]);
}
}
const paths = new Array(D.length);
const dp = new Array(D.length);
for (let i = 0; i < dp.length; i += 1) {
paths[i] = new Array(m + 1).fill(0);
dp[i] = new Array(m + 1);
for (let j = 0; j <= m; j += 1) {
dp[i][j] = new Array(D[i] + 2).fill(0);
for (let k = 1; k <= D[i]; k += 1) {
if (j === 0) {
dp[i][j][k] = Number(k === x[i]);
} else {
dp[i][j][k] = add(dp[i][j - 1][k - 1], dp[i][j - 1][k + 1]);
}
paths[i][j] = add(paths[i][j], dp[i][j][k]);
}
}
}
const acc = new Array(D.length);
acc[0] = paths[0];
for (let i = 1; i < D.length; i += 1) {
acc[i] = new Array(m + 1).fill(0);
for (let j = 0; j <= m; j += 1) {
for (let k = 0; k <= j; k += 1) {
const current = mul(acc[i - 1][k], binom[j][k], paths[i][j - k]);
acc[i][j] = add(acc[i][j], current);
}
}
}
return acc[D.length - 1][m];
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const nm = readLine().split(' ');
const n = parseInt(nm[0], 10);
const m = parseInt(nm[1], 10);
const x = readLine().split(' ').map(xTemp => parseInt(xTemp, 10));
const D = readLine().split(' ').map(DTemp => parseInt(DTemp, 10));
let result = gridWalking(m, x, D);
ws.write(result + "\n");
}
ws.end();
}
Grid Walking Python Solution
#!/usr/bin/env python
import sys
MOD = 1000000007
def choose(n, k):
if k < 0 or k > n:
return 0
else:
p, q = 1, 1
for i in range(1, min(k, n - k) + 1):
p *= n
q *= i
n -= 1
return p // q
def count_ways(N, M, D):
ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
# Find all possible ways for all points and steps
for i in range(N):
# Initial counting of zeroth and first steps
for j in range(D[i]):
ways[i][0][j] = 1
if j > 0:
ways[i][1][j] += 1
if j < D[i] - 1:
ways[i][1][j] += 1
# Higher steps
for s in range(2, M + 1):
for j in range(D[i]):
if j > 0:
ways[i][s][j] += ways[i][s - 1][j - 1]
if j < D[i] - 1:
ways[i][s][j] += ways[i][s - 1][j + 1]
# Return total ways
return ways
if __name__ == '__main__':
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
N, M = list(map(int, sys.stdin.readline().split()))
X = list(map(int, sys.stdin.readline().split()))
D = list(map(int, sys.stdin.readline().split()))
# Count the possible ways for each individual dimension
ways = count_ways(N, M, D)
# Compute totals
total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
for i in range(1, N):
for j in reversed(range(1, M + 1)):
k = j
while k >= 0 and (j, k) not in c:
c[(j, k)] = choose(j, k)
k -= 1
total[j] = sum(total[k] * c[(j, k)] * ways[i][j - k][X[i] - 1] for k in range(j + 1))
print(total[M] % MOD)