zzzrf：20 届秋招。
给定骑士在棋盘上的 初始 位置(一个 2 进制矩阵 0 表示空 1 表示有障碍物)，找到到达 终点 的最短路线，返回路线的长度。如果骑士不能到达则返回 -1 。
- 起点跟终点必定为空.
- 骑士不能碰到障碍物.
- 路径长度指骑士走的步数.
点此在线做题
说明
如果骑士的位置为 (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)
样例
例 1:
输入:
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2]
输出: 2
解释:
[2,0]->[0,1]->[2,2]
例 2:
输入:
[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2]
输出:-1
算法：BFS
朴素 BFS 搜搜最短路，BFS 概括来说就是像雷达一样，一层一层进行寻找目标点。当找到目标点后进行回溯。从而找到最佳路径。也就是说每走一步都要找到到达该点的最短的路径，最终得到到达所有点的最短路径，这题每一次的下一步做了规定，按照日字形跳到下一步。
- 根据下一跳位置建立方向数组
- dx=[1, 1, 2, 2, -1, -1, -2, -2]
- dy=[2, -2, 1, -1, 2, -2, 1, -1]
- 遍历八个方向，进行搜索
- 用 grid 数组标注是否访问过某点
- 注意判断下一跳的位置是否越界
复杂度分析
- 时间复杂度 O(n*m)
- 最多跑一边图 n 为图的行数，m 为图的列数，最多跑一边图，即 n*m
- 空间复杂度 O(n*m)
- 所有点的信息 n 为图的行数，m 为图的列数
public class Solution {
/**
* @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) {
int n = grid.length,m = grid[0].length;
if (n == 0 || m == 0) {
return -1;
}
int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
Queue<Point> queue = new LinkedList<>();
queue.offer(source);
grid[source.x][source.y] = true;
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
Point cur = queue.poll();
//到达终点，返回距离
if (cur.x == destination.x && cur.y == destination.y) {
return ans;
}
for (int i = 0; i < 8; i++) {
Point next = new Point (
cur.x + dx[i],
cur.y + dy[i]
);
//判断下一条可否到达
if (is_in_bound(next,n,m) && grid[next.x][next.y] == false) {
queue.offer(next);
grid[next.x][next.y] = true;
}
}
}
ans++;
}
return -1;
}
//判断是否越界
private boolean is_in_bound(Point next,int n,int m) {
return 0 <= next.x && next.x < n && 0 <= next.y && next.y < m;
}
}
猪场的待遇咋样啊。。
赚点辛苦费，欢迎各位老板&大佬咨询购买惠普产品Caan07：[赚点辛苦费] 主营惠普商用 PC/商务笔记本，保修一切按照惠普官方来执行。 贴图并不是所有型号和配置，有些产品特定工厂生产，或者有些型号不支持 CTO 特配，麻烦微信确认型号再确定是否支持特配。 有 INTEL 平台的，也有 AMD 平台的，也有国产芯片机型（不支持 CTO ） 品牌机，价格肯定不被各位 DIY 大佬看上，希望各位 DIY 大…
PHP中的“and”和“&&”运算符之间有什么区别吗？ - php我有以下代码，不认为并且不是必需的，即应该使用&&，因为没有什么可以分配左边的部分？if($_REQUEST['foo'] != 'abc' and $_REQUEST['bar'] == 'def') { echo "all your base…
有知乎的大佬吗，请问你们禁言算法怎么做的，怎么禁言如此频繁，隔一天禁言我一次YIFZ：现在我只要在涉及商品下面回答问题，不管我说什么，哪怕文字里什么商品都没有，什么品牌都没有，也照样禁言我，简直没完没了。 你们算法是不是当一个用户被禁言多了，误伤多了，不管申诉成功没，每隔几天禁言一次，一直到账号永久禁言为止。
路由算法xiaosenlin1：假设有 5000 个小房子 有入口和出口 现在求 某一个入口到某一个出口的 最短 10 条路径有没有大师做过类似的 计算nulI：之前用 pg 库的 pgRouting 做过。或者看下算法里图的那块手写？
如何使OR(||)和AND(&&)语句协同工作？的PHP - php我无法使此代码正常工作if ($title != 'Main' || $nSpace == 56 || $nSpace == 30 && $ifHome != 361) 所以我同意了这个代码if ($title != 'ArticleCategories' || $nSpace == 1) if ($n…