我关于这个算法的 Python 代码有什么问题?
What's wrong with my Python code about this algorithm?
有一个游戏。每个人有一个 10 * 10 的格子板。游戏开始前,他们需要在棋盘上放置三个 "planes"。问题是:平面放置有多少种可能?
这是一架飞机。
这是放置飞机的两种合法方式。平面的放置不能重叠,可以空隙插入
我的代码如下:
class Plane():
def __init__(self, x, y, direction):
self.x = x
self.y = y
self.direction = direction
@property
def body(self):
x = self.x
y = self.y
if self.direction == "up":
return[(x-2, y-1), (x-1, y-1), (x, y-1),
(x+1, y-1), (x+2, y-1), (x, y-2),
(x-1, y-3), (x, y-3), (x+1, y-3)]
elif self.direction == "down":
return[(x-2, y+1), (x-1, y+1), (x, y+1),
(x+1, y+1), (x+2, y+1), (x, y+2),
(x-1, y+3), (x, y+3), (x+1, y+3)]
elif self.direction == "left":
return[(x+1, y+2), (x+1, y+1), (x+1, y),
(x+1, y-1), (x+1, y-2), (x+2, y),
(x+3, y+1), (x+3, y), (x+3, y-1)]
elif self.direction == "right":
return[(x-1, y+2), (x-1, y+1), (x-1, y),
(x-1, y-1), (x-1, y-2), (x-2, y),
(x-3, y+1), (x-3, y), (x-3, y-1)]
@property
def check(self):
global chart
for x in self.body:
if x[0]<0 or x[0]>9 or x[1]<0 or x[1]>9 or chart[x[0]][x[1]] != 0:
return False
return True
def recursion(plane):
global chart, plane_list
if plane.check:
x = plane.x
y = plane.y
plane_list.append(plane)
chart[x][y] = 2
for j in plane.body:
chart[j[0]][j[1]] = 1
if x!= 9:
find_plane(x+1, y)
else:
find_plane(0, y+1)
plane_list.remove(plane)
chart[x][y] = 0
for j in plane.body:
chart[j[0]][j[1]] = 0
def find_plane(startx, starty):
global method_list, chart, plane_list
if len(plane_list) == 3:
method_list.append(plane_list)
return
if startx == 9 and starty == 9:
return
for x in range(10):
for y in range(10):
if (x > startx or y > starty) and (chart[x][y] == 0):
recursion(Plane(x, y, "up"))
recursion(Plane(x, y, "down"))
recursion(Plane(x, y, "left"))
recursion(Plane(x, y, "right"))
if __name__ == "__main__":
method_list = []
chart = [[0]*10 for i in [0]*10]
plane_list = []
find_plane(0, 0)
print(method_list)
我有问题:
- 这是method_list我终于得到了:
此处截图不完整。实际上,method_list由174631[]组成。很纳闷,因为我的代码逻辑是,只有当plane list的长度为3时,plane_list才会加到method_list上。我不明白为什么 method_list 是由一堆空列表组成的。
- 我的答案174631是错误的。我在网上搜索了这个问题,找到了这篇文章(中文)。
https://blog.csdn.net/GGN_2015/article/details/91295002
翻译:经过DFS,我们发现9*9的飞机轰炸游戏有8744种放置方案。如果棋盘的大小为10×10,方案总数为66816.
但是我的答案是66816的好几倍。算法我想了半天,还是不知道哪里错了。希望得到解答。
我花了一些时间得到了 66816。
我会尽力回答:
1。
整个 method_list
是对一个列表的引用列表 - plane_list
。
当 plane_list
为空时,则 method_list
的所有元素都为空...
plane_list
为空,因为您删除了所有元素。
您应该将 method_list.append(plane_list)
替换为 method_list.append(plane_list.copy())
.
2。
这段代码背后的逻辑真的很糟糕:
if x!= 9:
find_plane(x+1, y)
else:
find_plane(0, y+1)
我明白你想在这里做什么,但你做错了。所以...不要这样做。不要试图在 plane_list 中有某种顺序。
就这样做:
find_plane(0, 0)
那么您将在 method_list
中有重复项:
平面可以按以下顺序排列:(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).
同一个位置有6份。
所以...你应该将 len(method_list) 除以 6.
有一个游戏。每个人有一个 10 * 10 的格子板。游戏开始前,他们需要在棋盘上放置三个 "planes"。问题是:平面放置有多少种可能?
这是一架飞机。
这是放置飞机的两种合法方式。平面的放置不能重叠,可以空隙插入
我的代码如下:
class Plane():
def __init__(self, x, y, direction):
self.x = x
self.y = y
self.direction = direction
@property
def body(self):
x = self.x
y = self.y
if self.direction == "up":
return[(x-2, y-1), (x-1, y-1), (x, y-1),
(x+1, y-1), (x+2, y-1), (x, y-2),
(x-1, y-3), (x, y-3), (x+1, y-3)]
elif self.direction == "down":
return[(x-2, y+1), (x-1, y+1), (x, y+1),
(x+1, y+1), (x+2, y+1), (x, y+2),
(x-1, y+3), (x, y+3), (x+1, y+3)]
elif self.direction == "left":
return[(x+1, y+2), (x+1, y+1), (x+1, y),
(x+1, y-1), (x+1, y-2), (x+2, y),
(x+3, y+1), (x+3, y), (x+3, y-1)]
elif self.direction == "right":
return[(x-1, y+2), (x-1, y+1), (x-1, y),
(x-1, y-1), (x-1, y-2), (x-2, y),
(x-3, y+1), (x-3, y), (x-3, y-1)]
@property
def check(self):
global chart
for x in self.body:
if x[0]<0 or x[0]>9 or x[1]<0 or x[1]>9 or chart[x[0]][x[1]] != 0:
return False
return True
def recursion(plane):
global chart, plane_list
if plane.check:
x = plane.x
y = plane.y
plane_list.append(plane)
chart[x][y] = 2
for j in plane.body:
chart[j[0]][j[1]] = 1
if x!= 9:
find_plane(x+1, y)
else:
find_plane(0, y+1)
plane_list.remove(plane)
chart[x][y] = 0
for j in plane.body:
chart[j[0]][j[1]] = 0
def find_plane(startx, starty):
global method_list, chart, plane_list
if len(plane_list) == 3:
method_list.append(plane_list)
return
if startx == 9 and starty == 9:
return
for x in range(10):
for y in range(10):
if (x > startx or y > starty) and (chart[x][y] == 0):
recursion(Plane(x, y, "up"))
recursion(Plane(x, y, "down"))
recursion(Plane(x, y, "left"))
recursion(Plane(x, y, "right"))
if __name__ == "__main__":
method_list = []
chart = [[0]*10 for i in [0]*10]
plane_list = []
find_plane(0, 0)
print(method_list)
我有问题:
- 这是method_list我终于得到了:
此处截图不完整。实际上,method_list由174631[]组成。很纳闷,因为我的代码逻辑是,只有当plane list的长度为3时,plane_list才会加到method_list上。我不明白为什么 method_list 是由一堆空列表组成的。
- 我的答案174631是错误的。我在网上搜索了这个问题,找到了这篇文章(中文)。 https://blog.csdn.net/GGN_2015/article/details/91295002
翻译:经过DFS,我们发现9*9的飞机轰炸游戏有8744种放置方案。如果棋盘的大小为10×10,方案总数为66816.
但是我的答案是66816的好几倍。算法我想了半天,还是不知道哪里错了。希望得到解答。
我花了一些时间得到了 66816。 我会尽力回答:
1。
整个 method_list
是对一个列表的引用列表 - plane_list
。
当 plane_list
为空时,则 method_list
的所有元素都为空...
plane_list
为空,因为您删除了所有元素。
您应该将 method_list.append(plane_list)
替换为 method_list.append(plane_list.copy())
.
2。 这段代码背后的逻辑真的很糟糕:
if x!= 9:
find_plane(x+1, y)
else:
find_plane(0, y+1)
我明白你想在这里做什么,但你做错了。所以...不要这样做。不要试图在 plane_list 中有某种顺序。 就这样做:
find_plane(0, 0)
那么您将在 method_list
中有重复项:
平面可以按以下顺序排列:(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).
同一个位置有6份。
所以...你应该将 len(method_list) 除以 6.