hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Snakes and Ladders
Problem : 909. Snakes and Ladders
Problem Link : leetcode.com/problems/snakes-and-ladders/
Companies Asked : Uber, Adobe, Amazon, Google, Microsoft, Capital One, Goldman Sachs
Approach:
The problem is said to find out the steps we need to move from (N-1, 0) to (0,0) using the per-step moves available in a die (6-faced).
The only catch is if we go in a cell (x, y) that has a value, V other than -1, we need to move at the cell, V that is written on the cell (x,y).
The very first understanding I acquired is when I need to derive the cell (x y) from a value, V then, it is good to deserialize the coordinates according to the values.
In our case, we need to deserialize the cells according to the number from 1 to N^2.
Once we are done, we now start with the number 1. Our target is to move at number N^2.
Now consider a number, X. As we can have any number between 1 - 6 ( need to roll a die), we will find the next numbered cell by adding a side value to X. That is X + 1, X + 2, X + 3, X + 4, X + 5, X + 6. (1, 2, 3, 4, 5, 6 = side values). Hence we need to forward by 1-6 units from X.
While moving forward from X, if a cell has the number -1 then we are OK to be on that cell. If we have a number other than -1, then we need to move that cell.
However, that cell can be a lesser-numbered cell than the current one. This means we need to go near cell numbered 1. Instead of moving forward, we moved actually backward. And even if, we start from the backward cell, there is a very high chance to fall on the current cell. That means we can fall into an infinite loop.
Now to optimize this calculation, what we need to do is, we need to put a flag for every single cell, that we have completed visiting. So now, whenever we are in a position that has already been visited we can skip traversing that cell and keep moving to the next cell.
Once we move at cell N^2, return the step count.
If we have no more cells to visit and we do not find the N^2 cell, then return -1.
Time and Space Complexity:
Time Complexity: O(N^2)
Space Complexity: O(N^2)
Code [C++]
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
vector<vector<int>>cell(n*n+1, vector<int>(2));
int cellNo = 1, st = 0;
for(int i=n-1; i>=0; i--){
for(int j=0; j<n && !st; j++){
cell[cellNo++] = {i, j};
}
for(int j=n-1; j>=0 && st; j--){
cell[cellNo++] = {i, j};
}
st = st ^ 1;
}
queue<int>coord;
coord.push(1);
int step = 1;
vector<bool>used(n*n+1, false);
while(!coord.empty()){
int qsize = coord.size();
while(qsize--){
int top = coord.front();
coord.pop();
for(int i=1; i<=6; i++){
int next = top + i;
int x = cell[next][0], y = cell[next][1];
if(board[x][y] != -1){
next = board[x][y];
}
if(used[next]) continue;
if(next == n*n) return step;
used[next] = true;
coord.push(next);
}
}
step++;
}
return -1;
}
};