The city of Looneywalks has a rectangular grid of roads. One of the favorite pastimes of the folks at Looneywalks is to wander around the blocks. While they could take the shortest path, more often, they retrace their steps and engage themselves in finding the number of ways of reaching the destination with a given number of steps.
For example, in the figure above a block is shown with 8 blocks and roads around them. Any walk is a series of symbols U, R, L, D where by U we mean moving one block towards north, R, moving one block East, L moving one block West and D moving one block South. One such path for the above reaching the upper right corner from lower left corner is RRRRUU. This path has length 6 (the number of symbols in the path), which is the shortest pat (that do not go outside the grid)h between the two points. If we enumerate all such shortest paths of length 6, there are 15 of them. You are given the layout of the roads at Looneywalks.
Given a starting point, S ending point E and the length k of the path, write a program to find the number of valid paths from S to E that have length precisely k. A valid path is one that does not go outside the grid, and two path is one Every grid point is referred to by the X coordinate and a Y coordinate (the number of blocks east of the southwest corner, and the number of blocks north of the southwest corner). Thus the lower left corner in the above diagram is (0,0) and the top right corner is (4,2). The size of the block is given by two numbers, M and N. M is the number of rows in the grid, and N is the number of columns (in the grid above, M is 2 and N is 4).
Constraints:
M, N < 10, k < 20
Input:
The first line of the input has three comma separated integers M, N and k. The Dimensions of the grid are M blocks in rows, and N blocks in columns. The path length is given by k. The next line has four comma separated numbers giving the coordinates of the starting point and the ending point respectively.
Output:
One integer representing the number of valid paths from the starting point to ending point that have length precisely k.
Example 1
Input:
2 4 6
0 0 4 2
Output:
15
Explanation:
M is 2, and N is 4. The value of k is 6, and we are counting paths of length 6. The starting point is (0,0) and the end point is (4,2). The sketch of Loonewalks above is valid for this case. 6 is the length of the shortest path from the starting point to the ending point. Hence, we need to find the number of shortest paths. Each such path has 4 moves to the right (R) and two moves up (U). All paths having 4 Rs and 2 Us are valid, as none of them will take the walker outside the grid. This is just the number of arrangements of 4 R and 2U in any order, which can be seen to be 15. Hence the result is 15.
Example 2
Input:
3,3,6
1, 1, 3, 3
Output:
90
Explanation:
M=3, N=3,k=6. The starting and ending points are (1,1) and (3,3) respectively. The shortest path is of length 4, and has two R and two U in the path. An example is RRUU. As the desired path length is 6, we need to add an additional R (and the corresponding L) to all th shortest paths, or add an additional U (and the corresponding D) to all the shortest paths.
Let us first consider adding one R and one L. The shortest path will have two R, and if we look at only the horizontal part of the path, the new sequence could be one of three, LRRR, RLRR or RRLR. Note that RRRL is not valid, as it will go outside the grid. We need to add two U to each of these. In say RLRR, there are 5 ways if the two Us are together (UURLRR, RUULRR, and so on), and 10 wys if the Us are separate (URULRR, URLURR and so on), a total of 15 ways. Hence for all the three sequences, there are 45 paths if a RL pair is added. Similar considerations show that if we add a UD pair, there are another 45 paths. The total number of paths with length exactly 6 is therefore 45 + 45=90, which is the result.
Solution: In C
#include<stdio.h>
int path(int i,int j,int m,int n,int dm,int dn,int d){
if(d<0) return 0;
if(i==dn&&j==dm&&d==0) return 1;
if(i<0||j<0||i>n||j>m) return 0; //base cases
int sum=0;
sum+=path(i+1,j,m,n,dm,dn,d-1); // going east
sum+=path(i-1,j,m,n,dm,dn,d-1); // going west
sum+=path(i,j+1,m,n,dm,dn,d-1); // going north
sum+=path(i,j-1,m,n,dm,dn,d-1); // going south
return sum;
}
int main(){
int n,m,k;
scanf("%d %d %d",&m,&n,&k);
int i,j,dn,dm;
scanf("%d %d %d %d",&i,&j,&dm,&dn);
printf("%d",path(i,j,m,n,dm,dn,k));
}Solution: In Java
import java.util.*;
public class Main{
public static int path(int i,int j,int n,int m,int dn,int dm,int d){
if(d<0) return 0;
if(i==dn&&j==dm&&d==0) return 1;
if(i<0||j<0||i>n||j>m) return 0; //base cases
int sum=0;
sum+=path(i+1,j,n,m,dn,dm,d-1); // going east
sum+=path(i-1,j,n,m,dn,dm,d-1); // going west
sum+=path(i,j+1,n,m,dn,dm,d-1);// going north
sum+=path(i,j-1,n,m,dn,dm,d-1);// going south
return sum;
}
public static void main(String[] args){
int n,m,k;
Scanner ip=new Scanner(System.in);
n=ip.nextInt();
m=ip.nextInt();
k=ip.nextInt();
int i,j,dn,dm;
i=ip.nextInt();
j=ip.nextInt();
dn=ip.nextInt();
dm=ip.nextInt();
System.out.printf("%d",path(i,j,n,m,dn,dm,k));
}
}Solution: In Python 3
def path(i,j,n,m,dn,dm,d):
if d<0:
return 0
if(i==dn and j==dm and d==0):
return 1;
if(i<0 or j<0 or i>n or j>m):
return 0;
sum=0;
sum+=path(i+1,j,n,m,dn,dm,d-1);
sum+=path(i-1,j,n,m,dn,dm,d-1);
sum+=path(i,j+1,n,m,dn,dm,d-1);
sum+=path(i,j-1,n,m,dn,dm,d-1);
return sum;
n,m,k = list(map(int,(input().split())))
i,j,dn,dm = list(map(int,(input().split())))
print(path(i,j,n,m,dn,dm,k))Also Checkout