# snake and ladder problem solution using BFS

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[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

## Leave a Reply