前一阵子事情比较杂，因此停了很久才来更新博客。
最近在微信看到一个一笔画完的小游戏，大概规则是，在一个长方形的地图上，只画一笔遍历所有可达点。于是我用递归的思路，使用python写出了解题算法。
小游戏的截图：
算法思路如下：
地图可以表示为一个矩阵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
82class 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, [])
