BFS-knight

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 使用队列来做
# 从起点(sx,sy)存入队列,
# 从队列首位开始取出,然后执行进行方向移动。判断移动后的位置是否在棋盘内。是则存入队列,否则进入下一步
# 反复操作直到最后(x,y)=(ex,ey)


class Point(object):

    def __init__(self, x, y, step=0, path=[]):
        """
        knight的坐标系统
        :x: 点 x
        :y: 点 y
        :step: 记步
        :returns: 点对象
        """
        self.x = int(x)
        self.y = int(y)
        self.step = int(step)
        self.path = path

    def __repr__(self):
        return self.__str__()

    def __unicode__(self):
        return self.__str__()

    def __str__(self):
        return u"终点为<{0.x}, {0.y}>时,最短步数={0.step}".format(self)


def knight_move(size, s_point, e_point):
    """
    BFS knight movement
    :param size: 棋盘大小
    :param s_point: 起始点
    :param e_point: 终点
    :returns: 终点以及最短步数
    """
    size = int(size)
    board = [[0 for tmp_y in range(size)] for tmp_x in range(size)]
    queue = [s_point]  # 搜寻队列
    rules = ((1, 2), (2, 1),  # 1
             (1, -2), (2, -1),  # 4
             (-1, -2), (-2, -1),  # 3
             (-2, 1), (-1, 2))  # 2

    while queue:
        s_point = queue.pop(0)  # 取点
        if s_point.x == e_point.x and s_point.y == e_point.y:
            return s_point

        for direction in rules:

            next_point = Point(s_point.x + direction[0],
                               s_point.y + direction[1],
                               s_point.step + 1, )

            if (0 <= next_point.x < size and 0 <= next_point.y < size
                    and not board[next_point.y][next_point.x]):
                # 检查新的点是否有效且在图上
                next_point.path = s_point.path + [next_point]
                queue.append(next_point)
                board[next_point.y][next_point.x] = 1


result = knight_move(300, Point(0, 0), Point(11, 11))

print(result)

updatedupdated2020-06-202020-06-20
加载评论