九章算法 | 骑士的最短路线-BFS

爱被打了一巴掌 2022-10-07 03:55 51阅读 0赞

### 文章目录 ###

*   *  题解分析
     *  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

起点跟终点必定为空.  
骑士不能碰到障碍物.  
路径长度指骑士走的步数.

样例  
例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;
                    }
                    //判断此处是否已经走过了
                    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) //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 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 - 与指定值相关联的键。  
value - 与指定键关联的值。

返回值：当存在这个key的时候,会覆盖掉原来的value并返回oldvalue,也就是旧值。  
对返回值的进一步解释：  
如果没有键映射，则返回NULL。  
该函数返回与指定键关联的旧值。  
这个操作不管啥条件都会覆盖旧的。

## map-get() ##

get（key）：  
Key - 其关联值将被返回的键。  
返回值：指定键映射到的值，如果此映射不包含键的映射，则为NULL。

返回值进一步阐述：  
使用get函数，那么应该有先调用put函数对m表进行存储，不然肯定是返回null；  
由于m表的存储跟put函数有关，在实际工程应用中get返回值是受到put函数影响的。

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