算法描述
代码实现
import copy
m = [
[0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, ],
[1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, ],
[0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, ],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, ],
[0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, ],
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, ],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, ],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, ],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, ],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, ],
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, ],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, ],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, ],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, ],
[0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, ],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, ],
]
LEFT = "Left"
RIGHT = "Right"
UP = "Up"
DOWN = "Down"
class Map:
def __init__(self, m):
self.m = m
self.result = copy.deepcopy(m)
self.current = [0, 0]
self.direction = RIGHT
self.height = len(m)
self.width = len(m[0])
self.left_translations = dict(Right=UP, Up=LEFT, Left=DOWN, Down=RIGHT)
self.right_translations = dict(Right=DOWN, Up=RIGHT, Left=UP, Down=LEFT)
def get_next_position(self, direction):
if direction == UP:
return [self.current[0], self.current[1]-1]
elif direction == RIGHT:
return [self.current[0]+1, self.current[1]]
elif direction == DOWN:
return [self.current[0], self.current[1]+1]
elif direction == LEFT:
return [self.current[0]-1, self.current[1]]
else:
raise "invalid direction"
def is_available(self, position) -> bool:
if position[0] < 0 or position[0] >= self.width or position[1] < 0 or position[1] >= self.height:
return False
return self.m[position[1]][position[0]] == 0
def execute(self):
step = 1
self.show(step)
while True:
new_direction = self.right_translations[self.direction]
next_position = self.get_next_position(new_direction)
if self.is_available(next_position):
self.direction = new_direction
if self.has_change(next_position):
self.current = next_position
step += 1
self.show(step)
print("-----------------")
else:
self.direction = self.left_translations[self.direction]
if self.finished():
break
print("final result")
self.print_matrix(self.result)
def finished(self):
if self.current[0] == len(self.m[1])-1 and self.current[1] == len(self.m)-1:
return True
return False
def has_change(self, new_position):
return self.current[0] != new_position[0] or self.current[1] != new_position[1]
def show(self, step):
print("\n------------------ step : ", step)
#self.print_matrix(self.m)
for i in range(len(self.m)):
for j in range(len(self.m[i])):
if i == self.current[1] and j == self.current[0]:
print("X", end=" ")
else:
print(m[i][j], end=" ")
print()
self.result[self.current[1]][self.current[0]] = "X"
def print_matrix(self, matrix):
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i == self.current[1] and j == self.current[0]:
print("X", end=" ")
else:
print(matrix[i][j], end=" ")
print()
inst = Map(m)
inst.execute()
执行结果和经过路径
