Snake and Ladder

#include<bits/stdc++.h>
pair<int,int> findCord(int num,int n)
{
    int r = n-1 -(num-1)/n;
    int c = (num-1)%n;
    if(r%2 == n%2) c = n-1-c;
    return {r,c};
}
int minDiceThrowToLastCell(int **board, int n)
{
    vector<vector<int>> vis(n,vector<int>(n,0));
    queue<pair<int,int>> q;
    q.push({1,0});     // {intialStep , initailMove}
    int target = n*n;
    while(!q.empty())
    {
        int node = q.front().first;
        int Throw = q.front().second;
        q.pop();

        if(node == target) return Throw;

        for(int i=1;i<=6 ;i++)
        {
            if(node+i > target) continue;

            auto cor = findCord(node+i,n);
            int r = cor.first;
            int c = cor.second;

            if(vis[r][c]) continue;
            vis[r][c]=1;
            
            if(board[r][c]==-1) q.push({node+i,Throw+1});
            else q.push({board[r][c],Throw+1});
        }
    }
    return -1;
}

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static int[] findCoordinates(int cellNo,int n){
        int row = n - (cellNo - 1)/n  -1;
        int col = (cellNo - 1)%n;
        if(row%2 == n%2){
            col = n - 1 - col ;
            return new int[]{row,col};
        }else{
            return new int[]{row,col};
        }
    }

    public static int minDiceThrowToLastCell(int[][] board) {
        int n = board.length;

        boolean vis[][] = new boolean[n][n];

        Queue<Integer> q = new LinkedList<>();

        q.add(1);
        int steps = 0;
        vis[n-1][0] = true;

        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i<size;i++){
                int currNode = q.poll();
                // check for end
                if(currNode == n*n) return steps;

                for(int k = 1;k<=6;k++){
                    if(k+currNode>n*n) break;

                    int pos[] = findCoordinates(k+currNode,n);
                    int row = pos[0];
                    int col = pos[1];

                    if(vis[row][col] == true) continue;

                    
                    vis[row][col] = true;
                    if(board[row][col] == -1){
                        q.add(k + currNode);
                    }else{
                        q.add(board[row][col]);
                    }
                    
                }
            }
            // check for all possible moves with dice.

            steps++;
        }

        return -1;
    }
    
}

def find_coordinates(curr, n):
    r = n - (curr - 1) // n - 1
    c = (curr - 1) % n

    if r % 2 == n % 2:
        return [r, n - 1 - c]
    else:
        return [r, c]

def minDiceThrowToLastCell(board, n):
    steps = 0
    q = [1]
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[n - 1][0] = True

    while q:
        size = len(q)

        for _ in range(size):
            x = q.pop(0)
            if x == n * n:
                return steps

            for k in range(1, 7):
                if k + x > n * n:
                    break

                pos = find_coordinates(k + x, n)
                r, c = pos[0], pos[1]

                if visited[r][c]:
                    continue

                visited[r][c] = True

                if board[r][c] == -1:
                    q.append(k + x)
                else:
                    q.append(board[r][c])

        steps += 1
    return -1

#include<bits/stdc++.h>

int minDiceThrowToLastCell(int **board, int n)
{
  map<int, int> mp;
  bool ltr = true;
  int k = 1;

  for (int i = n - 1; i >= 0; i--) {
    if (ltr) {
      for (int j = 0; j < n; j++, k++) {
        if (board[i][j] != -1)
          mp[k] = board[i][j];
      }
    } else {
      for (int j = n - 1; j >= 0; j--, k++) {
        if (board[i][j] != -1)
          mp[k] = board[i][j];
      }
    }
    ltr = !ltr;
  }

  queue<pair<int, int>> q;
  q.push({1, 0});

  vector<int> vis(n * n + 1);
  vis[1] = 1;

  while (!q.empty()) {
    auto p = q.front();
    q.pop();

    int sq = p.first, steps = p.second;
    for (int i = 1; i <= 6; i++) {
      int newSq = sq + i;
      if (mp.count(newSq))
        newSq = mp[newSq];
    
        if(newSq > n *n)
            break;

      if (newSq == n * n)
        return steps + 1;

      if (!vis[newSq]) {
        vis[newSq] = 1;
        q.push({newSq, steps + 1});
      }
    }
  }

  return -1;
}

#include<bits/stdc++.h>

using namespace std;

int minDiceThrowToLastCell(int **board, int n)

{

    //  Write your code here

    int val = n*n;

    vector<pair<int,int>> cells(val+1);

    int label =1;

    vector<int> columns(n);

    iota(columns.begin(), columns.end(),0);

    for(int row=n-1; row>=0;row--){

        for(int column: columns){

            cells[label++] = {row,column};

        }

        reverse(columns.begin(),columns.end());

    }

    vector<int> dist(val+1,-1);

    queue<int> q;

    dist[1] =0;

    q.push(1);

    while(!q.empty()){

        int curr = q.front(); q.pop();

        for(int next=curr+1;next<=min(curr+6,val);next++){

            int row = cells[next].first,column = cells[next].second;

            int dest = board[row][column] != -1 ? board[row][column] : next;

            if(dist[dest] == -1){

                dist[dest] = dist[curr] +1;

                q.push(dest);

            }

        }

    }

  return dist[val];

}

#include "bits/stdc++.h"
using namespace std;
    vector<int> findCoordinates(int curr, int n){
        int r = n-(curr-1)/n - 1;
        int c = (curr - 1) % n;


        if(r%2 == n%2){
            return vector<int>{r,n-1-c};
        }
        else{
            return vector<int>{r,c};
        }
    }
int minDiceThrowToLastCell(int **board, int n)
{
    //  Write your code here
            // int n = board.size();
        int steps = 0;
        queue<int> q;
        bool visited[n][n];
        memset(visited,false,sizeof(visited));
        q.push(1);
        visited[n-1][0] = true;


        while(!q.empty()){
            int size = q.size();


            for(int i=0; i<size; i++){
                int x = q.front();
                q.pop();
                if(x == n*n) return steps;
                for(int k=1; k<=6; k++){
                    if(k+x > n*n) break;
                    vector<int> pos = findCoordinates(k+x,n);


                    int r = pos[0];
                    int c = pos[1];


                    if(visited[r][c] == true) continue;
                    visited[r][c] = true;
                    if(board[r][c] == -1){
                        q.push(k+x);
                    }
                    else{
                        q.push(board[r][c]);
                    }
                }
            }
            steps++;
        }
        return -1;
}

Hey everyone, creating this thread to discuss the interview problem - Snake and Ladder.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Snake and Ladder