LeetCode Medium: Snakes and Ladders

Here's a problem based on the classical snakes and ladders children's game

Problem Description: https://leetcode.com/problems/snakes-and-ladders

Solution Approach: BFS

Time Complexity: O(V) where V is the number of cells in the board-game and E = 6V.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution { public int snakesAndLadders(int[][] board) { int rows = board.length; int cols = board[0].length; int maxSq = rows*cols; boolean visited[] = new boolean[maxSq]; int[] pred = new int[maxSq+1]; // Allows to print the path as well. Alternatively, a dist[] incrementing at each time can be used too. Queue<Integer> squaresQ = new LinkedList<>(); squaresQ.add(1); visited[1] = true; pred[1] = 0; outer: while(!squaresQ.isEmpty()) { int sqOut = squaresQ.remove(); for (int i=1; i<=6; i++) { int neighbourSq = sqOut + i; if (neighbourSq > maxSq) break; int effRow = getEffRow(neighbourSq, rows, cols); int effCol = getEffCol(neighbourSq, rows, cols); if (board[effRow][effCol] != -1) { neighbourSq = board[effRow][effCol]; effRow = getEffRow(neighbourSq, rows, cols); effCol = getEffCol(neighbourSq, rows, cols); } if (neighbourSq == maxSq) { pred[neighbourSq] = sqOut; break outer; } if (!visited[neighbourSq]) { visited[neighbourSq] = true; pred[neighbourSq] = sqOut; // Alternatively, can do: dist[neighbourSq] = dist[sqOut]++; squaresQ.add(neighbourSq); } } } int cnt = 0; int predSq = maxSq; if (pred[predSq] == 0) return -1; while(predSq != 1) { cnt++; predSq = pred[predSq]; } return cnt; } private int getEffRow(int sq, int rows, int cols) { return (rows - 1 - (sq-1)/cols); } private int getEffCol(int sq, int rows, int cols) { int effCol = (sq -1) % cols; // 0 based if (((sq - 1)/cols + 1) % 2 == 0) // even row from bottom:1 based effCol = cols - 1 - effCol; return effCol; } }

Until next time,

Happy Coding!

Become a Patron!