Grid Walking


Problem Statement :


You are situated in an n dimensional grid at position (x[1],x[2],...,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. This implies that there are always 2*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 x[i], either x[i] <= 0 or x[i] >D[i].

For example, you start off in a 3 dimensional grid at position x = [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]}.

image
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 x[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 (10^9+7).

gridWalking has the following parameter(s):

m: an integer that represents the number of steps
x: an integer array where each x[i] represents a coordinate in the ith dimension where 1 <= i <=n
D: an integer array where each D[i] represents the upper limit of the axis in the ith dimension
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 x[i].
The third line of each test contains n space-separated integers D[i].

Constraints
1 <= t <= 10
1 <= n <= 10
1 <= m <= 300
1 <= D[i] <=100
1 <= x[i] <=D[i]

Output Format

Output one line for each test case. Since the answer can be really huge, output it modulo 10^9 + 7.



Solution :



title-img


                            Solution in C :

In C++ :





/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <memory.h>

const int maxn = 10;
const int maxm = 10000;
const long long modulo = 1000000007;

int D[maxn];
int X[maxn];

int n,m;
int solve(){
	std::cin>>n>>m;
	for (int i=0; i<n; i++)
		std::cin>>X[i];
	for (int i=0; i<n; i++)
		std::cin>>D[i];

	long long totalway[n][m+1];
	for (int i=0; i<n; i++){		
		long long total[D[i]];
		memset(total, 0, sizeof(total));
		total[X[i]-1] = 1;
		long long ans;
		totalway[i][0] = 1;
		for (int step=1; step<=m; step++){
			long long tmp[D[i]];
			for (int j=0; j<D[i]; j++){
				tmp[j] = 0;
				if (j>0) tmp[j] += total[j-1];
				if (j<D[i]-1) tmp[j] += total[j+1];
				tmp[j] %= modulo;
			}
			totalway[i][step] = 0;
			for (int j=0; j<D[i]; j++){
				total[j] = tmp[j];
				totalway[i][step] += total[j];
				totalway[i][step] %= modulo;
			}
        	}		
  	}	
	
	long long C[m+1][m+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]+C[i-1][j-1])%modulo;
		for (int j=i+1; j<=m; j++)
			C[i][j] = 0;
	}
		
	long long result[n][m+1];	
	for (int i=0; i<n; i++)
		for (int step=0; step<=m; step++){
			if (i==0){
				result[i][step] = totalway[i][step];
				continue;
			}
			result[i][step] = 0;
			for (int k=0; k<=step; k++){
				long long tmp = (result[i-1][k]*totalway[i][step-k])%modulo;
				tmp = tmp*C[step][step-k]%modulo;
				result[i][step] += tmp;
				result[i][step] %= modulo;
			}
			
		}
	std::cout<<result[n-1][m]<<std::endl;

}
int main(){
	int T;
	std::cin>>T;
	while (T>0){
		solve();
		T--;
	}
	return 0;
}








In Java :





import java.io.*;
import java.util.*;

public class Solution {
	
	public static final int MOD = 1000000007;
	public static final int MAXSTEPS = 310;
	
	public static void main(String[] args) throws IOException{
		long[][] pascals = new long[MAXSTEPS][];
		for (int i=0; i<MAXSTEPS; i++){
			pascals[i] = new long[i+1];
			pascals[i][0] = 1;
			for (int j=1; j<pascals[i].length; j++){
				pascals[i][j] = pascals[i-1][j-1];
				if (j<pascals[i-1].length)
					pascals[i][j] += pascals[i-1][j];
				pascals[i][j] %= MOD;
			}
		}
		
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	//BufferedReader in = new BufferedReader(new FileReader("test.in"));
	int cases = Integer.parseInt(in.readLine());
	for (int test = 0; test<cases; test++){
		StringTokenizer st = new StringTokenizer(in.readLine());
		int dims = Integer.parseInt(st.nextToken());
		int steps = Integer.parseInt(st.nextToken());
		int[] starts = new int[dims];
		st = new StringTokenizer(in.readLine());
		for (int i=0; i<dims; i++)
			starts[i] = Integer.parseInt(st.nextToken());
		int[] bounds = new int[dims];
		st = new StringTokenizer(in.readLine());
		for (int i=0; i<dims; i++)
			bounds[i] = Integer.parseInt(st.nextToken());
	
		long[] numWays = new long[steps+1];
		numWays[0] = 1;
		for (int i=0; i<dims; i++){
			long[] tempWays = new long[numWays.length];
			long[] nextDimWays = numPossSteps(starts[i], bounds[i], steps);

			for (int j=0; j<tempWays.length; j++){
				for (int k=0; k<=j; k++){
					long toAdd = (numWays[k]*nextDimWays[j-k])%MOD;
					toAdd *= pascals[j][k];
					tempWays[j] += toAdd%MOD;
					tempWays[j] %= MOD;
				}
			}
			numWays = tempWays;
		}
			
		System.out.println(numWays[steps]);
	}
}
	
	public static long[] numPossSteps(int start, int bound, int steps){
		long[] ret = new long[steps+1];
		ret[0] = 1;
		long[] trackLoc = new long[bound];
		trackLoc[start-1] = 1;
		for (int i=1; i<ret.length; i++){
			long[] nextTrack = new long[trackLoc.length];
			for (int j=0; j<trackLoc.length; j++){
				if (j>0)
					nextTrack[j] += trackLoc[j-1];
				if (j+1<bound)
					nextTrack[j] += trackLoc[j+1];
				nextTrack[j] %= MOD;
			}
			trackLoc = nextTrack;
			ret[i] = sum(trackLoc);
		}
		return ret;
	}
	
	public static long sum(long[] array){
		long sum = 0;
		for (int i=0; i<array.length; i++){
			sum+=array[i];
			sum %= MOD;
		}
		return sum;
	}
}








In C :





typedef long long int LL;
int mod=(int)(1e9+7);
int ways[302][102],fact[501],mi[501];
LL dp[12][302],tmp;
int x[12],d[12],i,j,k,t,n,m;
int res;
int raise(int pow,int power){
    res=1;
    while(power){
        if(power&1) res=((LL)res*pow)%mod;
        pow=((LL)pow*pow)%mod;
        power>>=1;
    }
    return res;
}
int modularInverse(int num){
    return raise(fact[num],mod-2);
}
int main(){
    fact[0]=1;
    for(i=1;i<=300;i+=1) fact[i]=((LL)fact[i-1]*i)%mod;
    mi[0]=1;
    for(i=1;i<=300;i+=1) mi[i]=modularInverse(i);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i+=1) scanf("%d",&x[i]);
        for(i=1;i<=n;i+=1) scanf("%d",&d[i]);
        dp[0][0]=1;
        for(k=1;k<=n;k+=1){
            for(j=1;j<=d[k];j+=1) ways[0][j]=1;
            for(i=1;i<=m;i+=1){
                for(j=1;j<=d[k];j+=1){
                    ways[i][j]=0;
                    if(j>1)
                    ways[i][j]+=ways[i-1][j-1];
                    if(ways[i][j]>=mod) ways[i][j]-=mod;
                    if(j<d[k])
                    ways[i][j]+=ways[i-1][j+1];
                    if(ways[i][j]>=mod) ways[i][j]-=mod;
                }
            }
            for(i=0;i<=m;i+=1){
                dp[k][i]=0;
                for(j=0;j<=i;j+=1){
                    tmp=(dp[k-1][i-j]*ways[j][x[k]])%mod;
                    dp[k][i]=(dp[k][i]+(tmp*mi[j])%mod);
                    if(dp[k][i]>=mod) dp[k][i]%=mod;
                }
            }
        }
        printf("%lld\n",(dp[n][m]*fact[m])%mod);
    }
    return 0;
}








In Python3 :





T = int(input())
MOD = 1000000007

C = [[0] * 400 for _ in range(400)]

C[0][0] = 1
for i in range(400):
    C[i][0], C[i][i] = 1, 1
    for j in range(1, i):
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD

for t in range(T):
    N, M = [int(c) for c in input().split()]
    X = [int(c) for c in input().split()]
    D = [int(c) for c in input().split()]

    # dp[N][D[i]][M+1]
    dp = [[[0] * (M+1) for j in range(D[i])] for i in range(N)]

    for i in range(N):
        for j in range(D[i]):
            dp[i][j][0] = 1

            if j > 0:
                dp[i][j][1] += 1
            if j < D[i] - 1:
                dp[i][j][1] += 1

        for m in range(2, M+1):
            for j in range(D[i]):
                if j > 0:
                    dp[i][j][m] += dp[i][j-1][m-1]
                if j < D[i] - 1:
                    dp[i][j][m] += dp[i][j+1][m-1]

    total = [dp[0][X[0]-1][m] for m in range(M+1)]

    for i in range(1, N):
        for j in reversed(range(1, M + 1)):
            total[j] = sum(total[k] * C[j][k] * dp[i][X[i]-1][j-k] for k in range(j+1)) 

    print(total[M] % MOD)
                        








View More Similar Problems

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →

Binary Search Tree : Insertion

You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <

View Solution →

Tree: Huffman Decoding

Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a 0 (zero). If on the right, they'll be a 1 (one). Only t

View Solution →

Binary Search Tree : Lowest Common Ancestor

You are given pointer to the root of the binary search tree and two values v1 and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree. In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3. Node 3 is the lowest node which has nodes and as descendants. Function Description Complete the function lca in the editor b

View Solution →

Swap Nodes [Algo]

A binary tree is a tree which is characterized by one of the following properties: It can be empty (null). It contains a root node only. It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees. In-order traversal is performed as Traverse the left subtree. Visit root. Traverse the right subtree. For this in-order traversal, start from

View Solution →