Untitled
plain_text
15 days ago
2.2 kB
1
Indexable
Never
class Solution { public: pair<int,int> cord(int n, int size) { int r = (n - 1) / size; // Subtract 1 from n to make it 0-based. int c = (n - 1) % size; // In the context of the game board, we subtract 1 from n to make it 0-based. // This assumes that square 1 is in the bottom-left corner of the board. // If square 1 is in the top-left corner, you can change the calculations accordingly. if (r % 2 == 1) { // If the row is odd, reverse the column. c = size - 1 - c; } r = size - 1 - r; // Reverse the row to match the board layout. return {r, c}; } int snakesAndLadders(vector<vector<int>>& board) { int size=board.size(); queue<pair<int,int>> q; // (square number , moves) unordered_set<int> vis; q.push({1,0}); vis.insert(1); while(!q.empty()){ int f=q.front().first; int moves=q.front().second; q.pop(); if(f==size*size) return moves; for(int i=1;i<=6 && f+i<=size*size;i++){ //do the initial jump and then check if you have landed on ladder or snake int next =f+i; //initial jump //if(vis.count(next)) continue; pair<int,int> p = cord(next,size); int r=p.first ,c=p.second; if(board[r][c]!=-1){ //good landing next=board[r][c]; } if(!vis.count(next)){ q.push({next,moves+1}); vis.insert(next); } } } return -1; } }; /* if(vis.count(f+i)) continue; pair<int,int> p=cord(f+i,size); int r=p.first,c=p.second; if(f+i==size*size) return moves+1; if(board[r][c]!=-1){ if(board[r][c]==size*size) return moves+1; q.push({board[r][c],moves+1}); vis.insert(board[r][c]); }else{ q.push({f+i,moves+1}); vis.insert(f+i); } */