力扣面试150题--蛇梯棋

Day 64

题目描述

思路

这题的难点在于我们需要将值转化为坐标（蛇形），专门写了一个函数Tohanglie来做这个事情。
其他的感觉没啥好说的就是一个简单的宽搜，需要注意的点是，梯子和蛇会跨越传送，这里不一定只往大的值去传送，所以我们需要考虑会不会出现环的问题（这类问题就通过visited数组来记录即可，不要重复访问）。

class Solution {public  int snakesAndLadders(int[][] board) {int n=board.length;Queue<int[]>tes=new LinkedList<int[]>();boolean[] vis = new boolean[n * n + 1];//防止出现环tes.offer(new int[]{1,0});//前面为值 后面为到该点的步数while (!tes.isEmpty()) {int[] be = tes.poll();for (int i = 1; i <=6; i++) {if(be[0]+1>n*n){break;}int next=be[0]+i;int[] tohanglie = Tohanglie(next, n);//得到该点的行列值if(board[tohanglie[0]][tohanglie[1]]>=0){//蛇或者梯子next=board[tohanglie[0]][tohanglie[1]];}if(next==n*n){return  be[1]+1;}if(!vis[next]){vis[next]=true;tes.offer(new int[]{next,be[1]+1});}}}return -1;//不能到达}public  int[] Tohanglie(int id, int n) {//将值转化为行列int i = (id - 1) / n, j = (id - 1) % n;if (i % 2 == 1) {j = n - 1 - j;}return new int[]{n - 1 - i, j};}
}