(LeetCode 每日一题) 909. 蛇梯棋 (广度优先搜索bfs)

思路：广度优先搜索bfs+队列，时间复杂度0(6*n^2)。
细节看注释

C++版本：

class Solution {
public:int snakesAndLadders(vector<vector<int>>& board) {int n=board.size();// vis[i]：表示i是否遍历过，避免环，重复遍历vector<bool> vis(n*n+1,false);// 队列，记录当前可以到达的位置queue<int> q;//初始化q.push(1);vis[1]=true;//距离，即次数int dis=-1;//不为空，则遍历while(q.size()){dis++;// 遍历当前dis达到的所有位置int cnt=q.size();while(cnt--){int t=q.front();q.pop();// 到达目的地，退出if(t==n*n){return dis;}// 遍历当前位置t，可达的所有位置kfor(int k=t+1;k<=min(t+6,n*n);k++){// 预处理出k在数组中的下标// k-1是为了方便处理，0~n*n-1int x=(k-1)/n,y=(k-1)%n;if(x%2!=0){y=n-1-y;}x=n-1-x;// tg是这一步可达的位置int tg=board[x][y];//小于0，说明不能跳，可达的位置就是k了if(tg<0) tg=k;//没遍历过if(vis[tg]==false){q.push(tg);vis[tg]=true;}}}}// 不存在return -1;}
};

JAVA版本：

class Solution {public int snakesAndLadders(int[][] board) {int n=board.length;boolean[] vis=new boolean[n*n+1];Arrays.fill(vis,false);Queue<Integer> qu=new ArrayDeque<>();qu.add(1);vis[1]=true;int dis=-1;while(!qu.isEmpty()){dis++;int cnt=qu.size();while(cnt!=0){cnt--;int t=qu.poll();if(t==n*n) return dis;for(int k=t+1;k<=Math.min(t+6,n*n);k++){int x=(k-1)/n;int y=(k-1)%n;if(x%2==1){y=n-1-y;}x=n-1-x;int tg=board[x][y];if(tg<0) tg=k;if(!vis[tg]){qu.add(tg);vis[tg]=true;}}}}return -1;}
}

Go版本：

func snakesAndLadders(board [][]int) int {n:=len(board)vis:=make([]bool,n*n+1)q:=[]int{1}vis[1]=truedis:=-1for len(q)>0 {dis++qu:=qq=nilfor _,t:=range qu {if t==n*n {return dis}for k:=t+1;k<=min(t+6,n*n);k++ {x,y:=(k-1)/n,(k-1)%nif x%2==1 {y=n-1-y}x=n-1-xtg:=board[x][y]if tg<0 {tg=k}if vis[tg]==false {vis[tg]=true;q=append(q,tg)}}}}return -1;
}