建设行业公司网站,黄山网站设计,wordpress中文网址,网站建设门户使用广度优先搜索来遍历从1到n*n的可能的路径。
这道题可以看作一个有向图#xff0c;每个值为x的节点指向x1点节点#xff0c;在蛇桥处#xff0c;是从x指向y
注意这里的x、x1、y都是值#xff0c;可以根据值计算出对应的行列值#xff0c;计算规则#xff1a; 假设值…使用广度优先搜索来遍历从1到n*n的可能的路径。
这道题可以看作一个有向图每个值为x的节点指向x1点节点在蛇桥处是从x指向y
注意这里的x、x1、y都是值可以根据值计算出对应的行列值计算规则 假设值为nxt 则对应的r为(nxt-1)/n由于nxt的值是从下往上依次递增而board的行列值是从上往下递增因此最终返回的行应该是n-1-(nxt-1)/n 对应的c为(nxt-1)%n由于是s型所以要根据r的奇偶来区分不同的c值当r为奇数时c取n-1-(nxt-1)%n当r为偶数时c取(nxt-1)%n这里的r是(nxt-1)/n也就是从下往上递增的。
除此之外还要注意蛇桥位置不计入步数所以在确定r和c后要判断这里是否存在蛇桥一步到位然后再判断一步到位之后的位置和n*n之间的关系。
class Solution {public int snakesAndLadders(int[][] board) {int n board.length;boolean[] vis new boolean[n * n 1];Queueint[] q new LinkedList();q.offer(new int[] {1, 0});while (!q.isEmpty()) {int[] p q.poll();// 扔骰子点数为1-6for (int i 1; i 6; i) {int nxt p[0] i;if (nxt n * n) break;int[] rc idx2rc(nxt, n);if (board[rc[0]][rc[1]] 0) nxt board[rc[0]][rc[1]];// 判断是否到终点应该放在判断蛇梯后面蛇梯不算步数。if (nxt n * n) return p[1] 1;if (!vis[nxt]) {vis[nxt] true;q.offer(new int[] {nxt, p[1] 1});}}}return -1;}private int[] idx2rc(int nxt, int n) {int r (nxt - 1) / n;int c r % 2 0 ? (nxt - 1) % n : n - 1 - (nxt - 1) % n;return new int[] {n - 1 - r, c};}
}
