我有兩個輸入
一個 NxM 城市網格，其中空白代表空地，X 代表填充地
例如
X XXX
X X
XXXX
XX X
格式為 List[List[str]]
和一個整數，表示所需的建筑物數量。
回傳所有可能展示位置的串列，即 List[List[List[str]]]
例如，使用上面的地圖和所需建筑物數量 = 3 的可能結果
XBXXX
BXB X
XXXX
XX X
另一個是
X XXX
X X
XXXXB
BXXBX
如果所需的建筑物數量 > 空地數量，則回傳適當的錯誤
我試過回溯。下面是我對解決方案的嘗試，但是“current_city_map”無法跟蹤上一級的狀態，例如當 building_count = 0 時“find_permutations”回傳時，當前城市地圖仍然具有最大的建筑數量它
`def can_place_building(xPos, yPos, city_map, building_code):
return city_map[yPos][xPos] == ' ':
def find_permutations(initial_city_map, current_city_map, building_code, required_building_count, possible_combinations):
if required_building_count == 0:
possible_combinations.append(current_city_map)
return
for x in range(len(current_city_map[0])):
for y in range(len(current_city_map)):
if can_place_building(x, y, current_city_map, building_code):
current_city_map[y][x] = building_code
find_permutations(initial_city_map, current_city_map, building_code, required_building_count - 1, possible_combinations)
def find_possible_combinations(initial_city_map, required_building_count: int) -> List:
building_code = 'B'
possible_combinations = []
current_city_map = copy.deepcopy(initial_city_map)
find_permutations(initial_city_map, current_city_map, building_code, required_building_count, possible_combinations)
return possible_combinations`
uj5u.com熱心網友回復：
我建議不要擁有當前和初始城市地圖，而是只擁有初始城市地圖，并將副本傳遞給遞回函式。所以，而不是：
current_city_map[y][x] = building_code
find_permutations(initial_city_map, current_city_map, building_code, required_building_count - 1, possible_combinations)
你會做類似的事情：
temp_map = copy.deepcopy(initial_city_map) temp_map[y][x] = building_code find_permutations(temp_map, building_code, required_building_count - 1, possible_combinations)
編輯：您當前的操作方式只是繼續編輯相同的 current_city_map，因此它永遠不會洗掉您在第一次運行時添加到其中的建筑物。您也許可以嘗試在途中的某個地方將其恢復為 initial_city_map，據我所知，這是您最初的意圖，但這似乎不必要地復雜。這應該更干凈。
uj5u.com熱心網友回復：
find_permutations 不接受定義的 required_building_count 。
def find_permutations(initial_city_map, current_city_map, building_code, possible_combinations):
必定是
def find_permutations(initial_city_map, current_city_map, building_code, required_building_count, possible_combinations):
除非 python 很神奇，而且我的經驗不足：)
編輯：這可能應該是評論，而不是答案。我的錯。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532357.html