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.

snake and ladder problem solution using BFS

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[10020];
/* enqueue data to rear and dequeue from front
*/
int front = 0;
int rear = 0;

int board[101];
bool visit[101];

int find_minDiceThrow()
{
	cell[rear].x = board[1];
	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



Related Contents to follow