Description
Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a sourceposition, find the shortest path to a destination position, return the length of the route.
Return -1 if destination cannot be reached.
source and destination must be empty.
Knight can not enter the barrier.
Path length refers to the number of steps the knight takes.
Clarification
If the knight is at (x, y), he can get to the following positions in one step:
(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)
Example
Example 1:
Input:
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2]
Output: 2
Explanation:
[2,0]->[0,1]->[2,2]
Example 2:
Input:
[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2]
Output:-1
思路：
给定起点和终点的无权图问题，必然用BFS，因为要知道步骤的长短， 我用了分层遍历的方法， 九章的答案采取的是另一种思路， 用dict存储每一步及其需要的步骤， 信息存储的比我的多。另外题中给source和destination时用了一个新的point类， 为了方便最好将其转化成传统数组，而不要像我直接用了，然后就得不停转换。我的代码在判断是否有效步骤的时候同时也判断了是否访问过，这点很好。
代码：
我的
答案的代码：
网友评论