ネズミの迷路問題
問題の説明:二次元配列を与えられ、配列の1は壁を表し、0は通路を表し、これによって配列は迷路図として示されてもよい.入り口の位置と出口の位置を指定して、通路があるかどうかを判断し、迷路から出る道を示します.
class Node(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.next = None
class TraceRecode(object):
def __init__(self):
self.first = None
self.last = None
def insert(self, x, y):
newNode = Node(x, y)
if self.first == None:
self.first = newNode
self.last = newNode
else:
self.last.next = newNode
self.last = newNode
def delete(self):
if self.first == None:
print(' ')
return
newNode = self.first
while newNode.next != self.last:
newNode = newNode.next
newNode.next = self.last.next #
self.last = newNode
def chkExit(MAZE, x, y, ex, ey):
'''
，
： （ ）
'''
if x == ex and y == ey:
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 2):
return 1
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 2 or MAZE[x][y + 1] == 1):
return 1
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 2 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
return 1
if (MAZE[x - 1][y] == 2 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
return 1
return 0
if __name__ == '__main__':
Exitx,Exity = 8,10
# ，0 ，1
MAZE = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ]
path = TraceRecode()
x, y = 1, 1 #
print(' （0 ）')
for i in range(10):
for j in range(12):
print(MAZE[i][j], end='')
print()
while x <= Exitx and y <= Exity:
MAZE[x][y] = 2 # 2
'''
， ， ， ， ，
'''
if MAZE[x - 1][y] == 0:
#
x -= 1
path.insert(x, y)
elif MAZE[x][y + 1] == 0:
#
y += 1
path.insert(x, y)
elif MAZE[x + 1][y] == 0:
#
x += 1
path.insert(x, y)
elif MAZE[x][y - 1] == 0:
#
y -= 1
path.insert(x, y)
#
elif chkExit(MAZE, x, y, Exitx, Exity) == 1:
break
else:
# ， ，
MAZE[x][y] = 2
path.delete() # ，
x = path.last.x
y = path.last.y
print(' （2 ）')
for i in range(10):
for j in range(12):
print(MAZE[i][j], end='')
print()