Posts pythonTip 24 一马当先
Post
Cancel

pythonTip 24 一马当先

题目描述:

下过象棋的人都知道,马只能走’日’字形(包括旋转90°的日),现在想象一下,给你一个n行m列网格棋盘, 棋盘的左下角有一匹马,请你计算至少需要几步可以将它移动到棋盘的右上角,若无法走到,则输出-1. 如n=1,m=2,则至少需要1步;若n=1,m=3,则输出-1。

分析

图形的搜索算法常见的有两种:深度优先(DFS)和 广度优先(BFS)

以下图为例说明两种算法的不同之处:

示例树

深度优先 不断沿着顶点的深度方向遍历,直到没有邻接点时再返回。

访问顺序: A-B-D-E-C-F-H-G

例如这里: 第一次从A到达B点时,还可以向 D 点访问,所以先访问点D。

访问完点D后,发现没有邻接点了,就返回到点B,然后再访问点E。

访问点E后,没有邻接点,就返回到点B,返回到点B的时候,发现下面的两个点都已经访问,就返回到点A。

然后从点A遍历到点C,再从C到F,再从F到H。最后访问点G。

广度优先

先访问与一个节点相邻的所有结点并且加入队列,然后再访问下一个节点。

访问顺序: A-B-C-D-E-F-G-H

解释:先访问和点A相邻的就是点 B 和 点 C。 队列: BC

然后从点B开始,访问到点DE, 队列 CDE

再从点C开始,访问到点 DEFG

然后…….

这就是我们深度优先和广度优先的两种遍历的结果。如果有兴趣,或者还不够明白,可以看看这个 https://www.jianshu.com/p/bff70b786bb6。

对于此题我们选用其中任何一种算法都是可以实现的。但是由于深度优先的遍历方式,我们需要遍历所有的节点才直到最少的步数是多少步。

如果是广度优先我们只需要遍历到 终点就可以返回了。因为我们是一层一层的去访问的,每一层就相当于一步,先找到一步能到的所有位置。

再找到两步可以到的所有位置。这样的话,我们就有可能少遍历一些点。这样就可以节约一点遍历的时间。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 当前的 马 可以去的8个位置, 相当于8 个方向
direction = [(-2, 1), (-2, -1), (2, 1), (2, -1), (-1, 2), (1, 2), (-1, -2), (1, -2)]


from queue import Queue
que = Queue()


# 开始位置 和 结束位置
now_x, now_y = n, 0

end_x, end_y = 0, m

# 我有这个,就可以同时记录 是否已经走过,还有 当前步数了
steps = {}

# 还要一个记录 当前是 第几步的操作。 想一想,,,


# 初始化, 将第一个位置加入队列
que.put((now_x, now_y))
steps[(now_x, now_y)] = 0

min_step = -1

while not que.empty():
    now_x, now_y = que.get()

    for dx, dy in direction:
        tx = now_x + dx
        ty = now_y + dy
        if tx > n or tx < 0 or ty > m or ty < 0:
            continue
        
        if tx == end_x and ty == end_y:
            min_step = steps[(now_x, now_y)] + 1
            break
        
        if (tx, ty) in steps.keys():
            continue
        
        steps[(tx, ty)] = steps[(now_x, now_y)] + 1
        que.put((tx, ty))
    if min_step > 0:
        break

print(min_step)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 23 365Or366

python 列表推导式生成多维数组

Trending Tags