Есть игра. У каждого человека есть клетчатая доска 10 * 10. Перед началом игры им нужно разместить три «самолета» на своей доске. Вопрос в том, сколько существует возможностей для размещения самолетов?
Это самолет.
Это два законных способа размещения самолетов. Размещение плоскости не может перекрываться, но может быть вставлено в зазор.
Мой код выглядит следующим образом:
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 []. Это меня сильно озадачило, потому что мой код logi c заключается в том, что только когда длина списка плоскостей равна 3, plane_list будет добавлен в method_list. Я не понял, почему method_list состоит из нескольких пустых списков.
Мой ответ 174631 неверен. Я искал Inte rnet для этой проблемы и нашел эту статью (китайский).
https://blog.csdn.net/GGN_2015/article/details/91295002 Перевод: После DFS мы обнаружили, что в игре с бомбардировкой 9 * 9 есть 8744 схемы размещения. Если размер шахматной доски равен 10 × 10, общее число схем составляет 66816.
Но мой ответ несколько раз равен 66816. Я долго думал об алгоритме и до сих пор не Знай, где я не прав. Надеюсь получить ответ.