# FROG JUMPING (NPTEL Week 2 Programming Assignment )

The latest hit on TV is a jumping game played on a giant rectangular chessboard. Each participant dresses up in a green frog suit and starts at the top left corner of the board. On every square there is a spring-loaded launcher that can propel the person either to the right or down.

write a program to calculate the smallest number of jumps needed to go from the top left corner to the bottom right corner, given the layout of the launchers on the board. **Read Full Problem Statement**

**Above problem can be solved using following approaches:**

Lets understand the problem statement once again. A Matrix (suppose M ) of dimension at most \(m \times n\) , (m,n<=250) where each block i.e M[i][j] corresponds to two values R and D as frog can jump up-to R blocks Right from current position or it can jump up-to D blocks Downward from the same position and your task is to determine the minimum number of jumps required to reach end of matrix.

**In order to solve this problem one has to face following set of problems:**

**How to store the data****Which data structure to use****How to reduce complexity****What is prerequisite to solve this problem.**

**Let’s answer these questions one by one:**

**How to Store the data**

Since it is mentioned that we have two values for each block of matrix. Hence it is advisable to use a ‘structure’ (in C, C++) with two values R and D .

struct frog{ int R,D; }M[250][250];

This will create a (2-D) matrix with two fields (R,D) (Instead of this we will use std::pair<int,int> (to create a 2-D matrix in C++).

**Which data structure to use**

Following are a list of Data Structure of which you must be aware of std::pair, std::queue. These data structure are already implemented in various language. You just have to understand the concept and how we can make use of these to solve this problem.

**How to reduce complexity**

We will discuss two approaches to solve this problem. Basically this problem can be solved using BFS to reduce complexity.

**What is prerequisite to solve this problem.**

- Basic understanding of how BFS works
- Basic matrix, queue operations.

**Naïve Method (Brute Force)**

By looking at problem we can see that a frog standing at a position (i,j) can take at most R or D steps i.e, 1<=step<=R or 1<=step<=D . A Brute force approach is that we will move to each position until we reach final destination which is last block of matrix. At each step a variable (dist) keeps track of how many steps we took till yet. If we reach at final we compare and store the minimum of all ways which leads to final block.

Finally we need to code the whole process.

#include<stdio.h> struct frog{ int D,R; }M[250][250]; int min_jump = 1e9; // assigning min_jump required to max value int n,m; // dimension m-> rows,n->columns void find_min_jump(int i, int j, int dist) { int k,Right,Down; if(i<0||j<0||i>=m||j>=n) // out of dimensions return ; if(i==m-1&&j==n-1) // if current position is destination { if(dist<min_jump) min_jump = dist; return; } Right=M[i][j].R; Down = M[i][j].D; for(k=1;k<=Right;k++) // Recurr through every possible position find_min_jump(i,j+k,dist+1); for(k=1;k<=Down;k++) find_min_jump(i+k,j,dist+1); } int main() { int i,j; // taking i/p scanf("%d%d",&m,&n); for( i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&M[i][j].R); for( i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&M[i][j].D); // end of i/p find_min_jump(0,0,0); printf("%d\n",min_jump);// printing final outcome return 0; }

This may sound very easy but the problem with this approach is that it takes quite large amount of time. **Hence we are with another optimal method.**

**Optimal method ****\(\mathcal O(m \times n)\):**

As we have discussed earlier that our problem is to reduce complexity and need not to recur for the same positions again and again, Lets come to approach.

Initially create a matrix Path[250][250] of integer type and assign each block to Max_Value except for staring block, assign it to ‘0’.

Starting from the first block we will **Push** current position in a **Queue** and for each step that we can take from that position do following steps:

- Update Path matrix of all reachable blocks with minimum steps.

For example: initially first block value is \(0\) and all blocks reachable from this will contain steps equal to
Path[a][b] = min ( Path[a][b] , Path[i][j]+1) ** **here
(i,j) is current position
&(a,b) is reachable block.

**Push**reachable position (a,b) to**Queue**only when its value is changed/updated.

This step is very significant to reduce complexity. How?

Take an example that if a position is reachable in two steps from one position, and using another path we reach at that step using 3 steps. Do we need to update that?? Our problem is about taking all over minimum steps to reach destination.

Think over it again.

- Repeat this step until
**Queue**becomes empty.

Following is code using above mentioned approach.

#include<bits/stdc++.h> using namespace std; struct frog{ int D,R; }M[250][250]; int n,m; // dimension m-> rows,n->columns int find_min_jump() { int Path[250][250]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) Path[i][j]=1e9; // assigning each element of Path to Max_Value Path[0][0]=0; pair<int,int> P; queue <pair<int,int> > Q; Q.push(make_pair(0,0)); while(!Q.empty()) // BFS { P=Q.front(); Q.pop(); int i,j; i=P.first; j=P.second; for(int k=1;k<=M[i][j].R;k++) { if(Path[i][j+k]>Path[i][j]+1) { Path[i][j+k]=Path[i][j]+1; Q.push(make_pair(i,j+k)); } } for(int k=1;k<=M[i][j].D;k++) { if(Path[i+k][j]>Path[i][j]+1) { Path[i+k][j]=Path[i][j]+1; Q.push(make_pair(i+k,j)); } } } return Path[m-1][n-1];// returning steps required to reach final block } int main() { int i,j; // taking i/p scanf("%d%d",&m,&n); for( i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&M[i][j].R); for( i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&M[i][j].D); // end of i/p printf("%d\n",find_min_jump());// printing final outcome return 0; }

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.