蛇梯棋 - C++力扣909题

题目链接：https://leetcode.com/problems/snakes-and-ladders/description/

解题思路

这个题目算是中等难度，考验着我们对题目的理解以及思路，本人也掉了一下坑才反应过来。首先我想到的还是 dfs ，但是发现如果用函数递归或者递推但是结束条件没设定好的话，很可能会掉进死循环里面（对，就是我这个垃圾），所以我们来换一个思路，我们用队列来进行（其实跟用函数没啥区别，单纯是我垃圾没设置好结束条件）。

首先因为棋盘走法有点复杂，我们不妨将其转换为一维数组，然后通过棋盘上的数字进行访问。之后就是我们可以把当前位置后面 6 个位置加入到队列里面来进行循环，直到 n * n 为止。如果在添加的时候发现有梯或者蛇，那么直接把目的地加入到队列而不用把原本的格子加入，这样就不用在外面写走梯或者蛇的程序了，也能节省一点时间。

最后我们把代码做一些优化基本上就能过了。

完整代码：

class Solution {
public:

    int snakesAndLadders(vector<vector<int>>& board) {
       int n = board.size();
       vector<int> movesCnt(n * (n + 1), -1);
       movesCnt[1] = 0;
       vector<int> newBoard(n * (n + 1), -1);
       int s = 1;
       for(int i = 0; i < n; i++) {
           for(int j = 0; j < n; j++) {
               newBoard[s++] = (i % 2 == 0) ? board[n - 1 - i][j] : board[n - 1 - i][n - j - 1];
           }
       }

       queue<int> q;
       q.push(1);

       while(q.size() > 0) {
            int now = q.front(); q.pop();
            if(movesCnt[n * n] != -1) break;
            if(now > n * n) continue;

            for(int i = 1; i <= 6; i++) {
                int dest = now + i;
                if(dest > n * n) break;
                if(newBoard[dest] != -1) dest = newBoard[dest];
                if(movesCnt[dest] == -1) {
                    q.push(dest);
                    movesCnt[dest] = movesCnt[now] + 1;
                }
            }
       }

       return movesCnt[n * n];
    }
};