• • Snake and Ladder problem solution using BFS (breadth first search). The problem is to find the minimum number of dice throws or minimum move to reach to the top right most corner. The movement of dice would start from position 1 and we have to reach at 31th position with minimum moves. ## How to solve

Test Cases:

```2
3
32 62
42 68
12 98
7
95 13
97 25
93 37
79 27
75 19
49 47
67 17
4
8 52
6 80
26 42
2 72
9
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 214```

The first line contains the number of tests, T. T testcases follow.

For each testcase, the first line contain N(Number of ladders) and after that N line follow. Each of the N line contain 2 integer representing the starting point and the ending point of a ladder respectively.

The next line contain integer M(Number of snakes) and after that M line follow. Each of the M line contain 2 integer representing the starting point and the ending point of a snake respectively.

```#include <cstdio>
#include <iostream>
using namespace std;

#define N 101

/* this data structure is used
as queue */
struct cell_
{
int x;
int step;
};
struct cell_ cell;
/* enqueue data to rear and dequeue from front
*/
int front = 0;
int rear = 0;

int board;
bool visit;

int find_minDiceThrow()
{
cell[rear].x = board;
cell[rear].step = 0;
rear++;

// store temp step and cell index
int s= -1;
int cellx=-1;
while (rear != front)
{
int x = cell[front].x;
int st = cell[front].step;
front++;
// update step and cell index
s = st;
cellx=x;
// if the index x is last cell of board
if (x == N - 1)
{
break;
}

for (int i = x + 1; i <= 6 + x && i < N; i++)
{
if (!visit[i])
{
visit[i] = 1;
// enqueue index x and step
cell[rear].x = board[i];
cell[rear].step = st + 1;
rear++;
}
}
}

// check whether we have reached at the last cell of board
if(cellx == N -1)
return s;
else
return -1;
}

int main() {

freopen("in.txt", "r", stdin);

int T = 0;
cin >> T;
for (int i = 0; i < T; i++)
{
for (int i = 0; i < 101; i++)
{
board[i] = i;
visit[i] = 0;
}

int l = 0;
int s = 0;
cin >> l;
for (int i = 0; i< l; i++)
{
int l_s = 0;
int l_e = 0;
cin >> l_s >> l_e;
board[l_s] = l_e;
}
cin >> s;
for (int i = 0; i < s; i++)
{
int s_s = 0;
int s_e = 0;
cin >> s_s >> s_e;
board[s_s] = s_e;
}
int ans = find_minDiceThrow();
if(ans != -1)
cout << ans << endl;
else
cout <<"-1"<<endl;

// reset for queue
rear = front = 0;

}
return 0;
}```

Ref:

https://www.hackerrank.com/challenges/the-quickest-way-up