微信一笔画完小游戏的解题算法

发表于 更新于 分类于
微信一笔画完小游戏的挂机算法。

前一阵子事情比较杂，因此停了很久才来更新博客。

最近在微信看到一个一笔画完的小游戏，大概规则是，在一个长方形的地图上，只画一笔遍历所有可达点。于是我用递归的思路，使用python写出了解题算法。

小游戏的截图：
base_img

算法思路如下：

地图可以表示为一个矩阵map，这个矩阵中，0表示该位置不可达，1则表示该位置是可达的。特殊地，初始点所在的位置记为1。

除此之外，我们需要一个与map相同大小的矩阵，来记录当前的位置是否被访问过。

接下来，我们用递归的思路去解决这个问题。
从初始点开始，每一个位置都有四种可能的方向。我们循环对这四种方向进行尝试，即从一个新的点去继续搜索，直至搜索不到返回false或者返回一个操作序列。

代码如下：

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
71
72
73
74
75
76
77
78
79
80
81
82
class OneLine(object):

    def __init__(self, row, col):
        '''
        map 是原地图 0表示位置不可用，1表示可用
        status 表示已经访问过的点，1表示未访问，0表示已访问
        :param row: 行
        :param col: 列
        '''
        self.map = np.zeros((row, col))
        self.status = np.ones((row, col))
        self.init = None

    def set_position_available(self, x, y):
        self.map[x][y] = 1

    def set_map(self, map):
        self.map = map

    def set_init_point(self, point):
        self.init = point
        self.status[point[0], point[1]] = 0
        self.state = self.map * self.status

    def is_finished(self, state):
        if (np.sum(state) == 0):
            return True
        else:
            return False

    def move_to(self, map, status, curr_point, op_code):
        next_status = copy.copy(status)

        if (op_code == 'r'):  # 右划
            next_point = [curr_point[0], curr_point[1] + 1]
        elif (op_code == 'l'):  # 左划
            next_point = [curr_point[0], curr_point[1] - 1]
        elif (op_code == 'u'):  # 上划
            next_point = [curr_point[0] - 1, curr_point[1]]
        elif (op_code == 'd'):  # 下划
            next_point = [curr_point[0] + 1, curr_point[1]]
        else:
            next_point = curr_point

        next_status[next_point[0], next_point[1]] = 0
        next_state = map * next_status
        return {'map': map, 'status': next_status, 'state': next_state, 'curr_point': next_point}

    def get_available_operation(self, state, curr_point):
        op_list = []
        dim = state.shape
        if (curr_point[0] > 0 and state[curr_point[0] - 1, curr_point[1]] == 1):
            op_list.append('u')
        if (curr_point[0] < dim[0] - 1 and state[curr_point[0] + 1, curr_point[1]] == 1):
            op_list.append('d')
        if (curr_point[1] > 0 and state[curr_point[0], curr_point[1] - 1] == 1):
            op_list.append('l')
        if (curr_point[1] < dim[1] - 1 and state[curr_point[0], curr_point[1] + 1] == 1):
            op_list.append('r')
        return op_list

    def search_path(self, map, status, state, curr_point, path):
        # 如果找到解，返回
        if (self.is_finished(state)):
            return path
        # 否则进行尝试
        available_op = self.get_available_operation(state, curr_point)
        # 如果当前没走到死路
        while (len(available_op) != 0):
            op = available_op.pop()
            mov = self.move_to(map, status, curr_point, op)
            path.append(op)
            p = self.search_path(mov['map'], mov['status'], mov['state'], mov['curr_point'], path)
            if (p != False):
                return p
        path.pop()
        return False

    def start_find(self):
        return self.search_path(self.map, self.status, self.state, self.init, [])


完整代码指路github