蛇梯棋

问题

蛇梯棋 原题链接：https://leetcode.cn/problems/snakes-and-ladders?envType=study-plan-v2&envId=top-interview-150

解法

本题难度为中等，一看就可以知道思路为BFS，只要做好条件的判断可以自然求出答案。个人在做的过程中，对于奇、偶行的方向判断陷入了困境，拆分了大量不同情况，最后放弃看了答案。看答案后明白答案对行数的判断真的很巧妙。他没有多余的判断，只借助本身的next值，通过numToId函数将值得到具体的行坐标和列坐标，且依据是奇数行还是偶数行（从下往上看）翻转列数保证了正确的顺序。返回时行数也翻转一下，即保证了他原本是从下往上变为从上往下，符合数组的正常顺序。

class Solution {
public:
    //巧妙的运用数字本身的特点来避免冗余的方向判断（该向左还是右？）
    pair<int,int> numToId(int next,int n){
        int r=(next-1)/n;
        int c=(next-1)%n;
        //从下往上数为奇数行则列坐标要反转，从右往左则将其翻转。
        if(r%2==1) c=n-1-c;
        //行坐标也要翻转，next定义为从下往上，坐标中体现为从上往下
        return {n-r-1,c};
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        int n=board.size();
        queue<pair<int,int>> q;
        vector<int> vis(n*n+1,0);//记录访问了的点
        q.push({1,0});//起始为1，所走的步数为0
        while(!q.empty()){
            auto tempPair=q.front();
            q.pop();
            for(int i=1;i<7;i++){
                int ne=tempPair.first+i,step=tempPair.second;
                if(ne>n*n) break;//结束此次循环
                //广搜不记录最小值（不像深搜），只需要看谁先到总点返回的就是最小值
                auto [r,c]=numToId(ne,n);
                if(board[r][c]!=-1) ne=board[r][c];
                if(ne==n*n) return step+1;
                if(!vis[ne]){//若该点没被访问才能走
                    vis[ne]=1;
                    q.push({ne,step+1});
                }
            }
        }
        return -1;
    }
};