leetcode 909. Snakes and Ladders 蛇梯棋-耗时100

Problem: 909. Snakes and Ladders 蛇梯棋

耗时100%，广度优先搜索，transform函数用来将标记转换到坐标，已经加入了状态标记，若是已经访问过的标记，不重复访问同一个标记，若是>0则跳到终点并标记，否则加入终点j并标记，从1可以跳到2 3 4 5 6 7，从2也可以跳到3，但是步数最少，所以提前标记true，2不再跳到3，只从1跳到3，相当是剪枝了

Code

class Solution { public: int n; pair<int, int> transform(int x) { x--; int row = x / n; int column = x % n; if((row&1)==1) { column = n - column - 1; } row = n - row - 1; return {row, column}; } bool status[600]; int snakesAndLadders(vector<vector<int>>& board) { n = board.size(); queue<int> qe; qe.push(1); status[1] = true; int now, step = 0, sz, nextMAX, nn = n * n; memset(status, 0, sizeof(status)); while(qe.empty()==false) { sz = qe.size(); step++; for(int i = 0; i < sz; i++) { now = qe.front(); qe.pop(); nextMAX = min(nn, now + 6); for(int j = now + 1; j <= nextMAX; j++) { auto [r, c] = transform(j); if(board[r][c] > 0) { if(status[board[r][c]] == true) { continue; } status[board[r][c]] = true; qe.push(board[r][c]); if(board[r][c] == nn) { return step; } } else if(status[j] == false){ status[j] = true; qe.push(j); if(j == nn) { return step; } } } } } return -1; } };