文章目錄

• • 題解分析
  • java-queue
  • map-containsKey()
  • map-put()
  • map-get()

題解分析

給定騎士在棋盤上的 初始 位置(一個2進制矩陣 0 表示空 1 表示有障礙物)，找到到達 終點 的最短路線，返回路線的長度。如果騎士不能到達則返回 -1 。
https://www.jiuzhang.com/solution/knight-shortest-path/?utm_source=sc-zhihuzl-lm

起點跟終點必定為空.
騎士不能碰到障礙物.
路徑長度指騎士走的步數(shù).

樣例
例1:

輸入:

[[0,0,0],[0,0,0],[0,0,0]] source = [2, 0] destination = [2, 2]

輸出: 2
解釋:
[2,0]->[0,1]->[2,2]

如果騎士的位置為 (x,y)，他下一步可以到達以下這些位置:

(x + 1, y + 2) (x + 1, y - 2) (x - 1, y + 2) (x - 1, y - 2) (x + 2, y + 1) (x + 2, y - 1) (x - 2, y + 1) (x - 2, y - 1) /*** Definition for a point.* class Point {* int x;* int y;* Point() { x = 0; y = 0; }* Point(int a, int b) { x = a; y = b; }* }*/public class Solution {public static final int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};public static final int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};/*** @param grid: a chessboard included 0 (false) and 1 (true)* @param source: a point* @param destination: a point* @return: the shortest path */public int shortestPath(boolean[][] grid, Point source, Point destination) {//棋盤不存在，起點不存在if (grid == null || grid.length == 0|| grid[0] == null || grid[0].length == 0) {return -1;}Queue<Point> queue = new ArrayDeque();Map<Integer, Integer> distance = new HashMap();int n = grid.length, m = grid[0].length;queue.offer(source);distance.put(source.x * m + source.y, 0);while (!queue.isEmpty()) {Point point = queue.poll();//走完了if (point.x == destination.x && point.y == destination.y) {return distance.get(point.x * m + point.y);}//找下一個走的點坐標for (int i = 0; i < 8; i++) {int adjX = point.x + dx[i];int adjY = point.y + dy[i];//走不通if (!isValid(adjX, adjY, grid)) {continue;}//判斷此處是否已經(jīng)走過了if (distance.containsKey(adjX * m + adjY)) {continue;}distance.put(adjX * m + adjY, distance.get(point.x * m + point.y) + 1);//走的格子坐標入隊queue.offer(new Point(adjX, adjY));}}return -1;}//是否走的通private boolean isValid(int x, int y, boolean[][] grid) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {return false;}return !grid[x][y];} }

java-queue

boolean add(E e) //將指定的元素插入此隊列（如果立即可行且不會違反容量限制），在成功時返回 true，如果當前沒有可用的空間，則拋出 IllegalStateException。 E element() //獲取，但是不移除此隊列的頭。 boolean offer(E e) //將指定的元素插入此隊列（如果立即可行且不會違反容量限制），當使用有容量限制的隊列時，此方法通常要優(yōu)于 add(E)，后者可能無法插入元素，而只是拋出一個異常。 E peek() //獲取但不移除此隊列的頭；如果此隊列為空，則返回 null。 E poll() //獲取并移除此隊列的頭，如果此隊列為空，則返回 null。 E remove() //獲取并移除此隊列的頭。

map-containsKey()

1 map是一個key和value的鍵值對的集合。有key和value鍵值對，就會有判斷是否有key。這方法就是containsKey方法。

if(map.containsKey("name")){ value=map.get("name").toString(); System.out.println("找到了name的值："+value); }

map-put()

put(K key, V value)
key - 與指定值相關聯(lián)的鍵。
value - 與指定鍵關聯(lián)的值。

返回值：當存在這個key的時候,會覆蓋掉原來的value并返回oldvalue,也就是舊值。
對返回值的進一步解釋：
如果沒有鍵映射，則返回NULL。
該函數(shù)返回與指定鍵關聯(lián)的舊值。
這個操作不管啥條件都會覆蓋舊的。

map-get()

get（key）：
Key - 其關聯(lián)值將被返回的鍵。
返回值：指定鍵映射到的值，如果此映射不包含鍵的映射，則為NULL。

返回值進一步闡述：
使用get函數(shù)，那么應該有先調用put函數(shù)對m表進行存儲，不然肯定是返回null；
由于m表的存儲跟put函數(shù)有關，在實際工程應用中get返回值是受到put函數(shù)影響的。

https://www.cnblogs.com/rogerelva55/p/shunxin.html

總結

以上是生活随笔為你收集整理的九章算法 | 骑士的最短路线-BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。