import heapq
import copy
地图定义
map_grid = [
[0, 0, 1, 0, 2],
[1, 0, 1, 0, 1],
[2, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 2, 0, 9]
]
start = (0, 0)
def heuristic(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
def astar(grid, start, goal):
rows, cols = len(grid), len(grid[0])
open_set = [(0, start)]
g_score = {start: 0}
came_from = {}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1]
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
neighbor = (current[0]+dx, current[1]+dy)
x, y = neighbor
if 0 <= x < rows and 0 <= y < cols and grid[x][y] != 1:
ng = g_score[current] + 1
if neighbor not in g_score or ng < g_score[neighbor]:
g_score[neighbor] = ng
priority = ng + heuristic(neighbor, goal)
heapq.heappush(open_set, (priority, neighbor))
came_from[neighbor] = current
return None
def find_items_and_exit(grid):
items, exit_point = [], None
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 2:
items.append((i, j))
elif grid[i][j] == 9:
exit_point = (i, j)
return sorted(items), exit_point
def collect_and_escape(grid, start):
items, exit_point = find_items_and_exit(grid)
current = start
all_path = [start]
for item in items:
path = astar(grid, current, item)
if not path:
print("无法到达物资点:", item)
return None
if len(path) > 1:
all_path.extend(path[1:]) # 跳过当前点
current = item
path = astar(grid, current, exit_point)
if not path:
print("无法到达撤离点")
return None
if len(path) > 1:
all_path.extend(path[1:])
return all_path
def print_map(grid, pos, collected):
symbol_map = {0: '.', 1: '#', 2: 'M', 9: 'E'}
temp = copy.deepcopy(grid)
x, y = pos
# 显示收集状态
for m in collected:
i, j = m
temp[i][j] = 0
for i in range(len(temp)):
line = ''
for j in range(len(temp[0])):
if (i,j) == pos:
line += 'Δ' # 三角洲队员
else:
line += symbol_map.get(temp[i][j], '?')
print(line)
print()
----------主程序----------
route = collect_and_escape(map_grid, start)
if route:
items, _ = find_items_and_exit(map_grid)
collected = []
print("行动路径如下 (Δ为队员，M物资，#障碍，E撤离点)：\n")
for idx, step in enumerate(route):
# 检查是否收集物资
if step in items and step not in collected:
collected.append(step)
text = "收集到物资!"
elif map_grid[step[0]][step[1]] == 9:
text = "到达撤离点，完成任务!"
else:
text = ""
print(f"步骤{idx+1}: 位置{step} {text}")
print_map(map_grid, step, collected)
else:
print("找不到完整行动路径")
import heapq
import copy
地图定义
map_grid = [
[0, 0, 1, 0, 2],
[1, 0, 1, 0, 1],
[2, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 2, 0, 9]
]
start = (0, 0)
def heuristic(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
def astar(grid, start, goal):
rows, cols = len(grid), len(grid[0])
open_set = [(0, start)]
g_score = {start: 0}
came_from = {}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1]
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
neighbor = (current[0]+dx, current[1]+dy)
x, y = neighbor
if 0 <= x < rows and 0 <= y < cols and grid[x][y] != 1:
ng = g_score[current] + 1
if neighbor not in g_score or ng < g_score[neighbor]:
g_score[neighbor] = ng
priority = ng + heuristic(neighbor, goal)
heapq.heappush(open_set, (priority, neighbor))
came_from[neighbor] = current
return None
def find_items_and_exit(grid):
items, exit_point = [], None
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 2:
items.append((i, j))
elif grid[i][j] == 9:
exit_point = (i, j)
return sorted(items), exit_point
def collect_and_escape(grid, start):
items, exit_point = find_items_and_exit(grid)
current = start
all_path = [start]
for item in items:
path = astar(grid, current, item)
if not path:
print("无法到达物资点:", item)
return None
if len(path) > 1:
all_path.extend(path[1:]) # 跳过当前点
current = item
path = astar(grid, current, exit_point)
if not path:
print("无法到达撤离点")
return None
if len(path) > 1:
all_path.extend(path[1:])
return all_path
def print_map(grid, pos, collected):
symbol_map = {0: '.', 1: '#', 2: 'M', 9: 'E'}
temp = copy.deepcopy(grid)
x, y = pos
# 显示收集状态
for m in collected:
i, j = m
temp[i][j] = 0
for i in range(len(temp)):
line = ''
for j in range(len(temp[0])):
if (i,j) == pos:
line += 'Δ' # 三角洲队员
else:
line += symbol_map.get(temp[i][j], '?')
print(line)
print()
----------主程序----------
route = collect_and_escape(map_grid, start)
if route:
items, _ = find_items_and_exit(map_grid)
collected = []
print("行动路径如下 (Δ为队员，M物资，#障碍，E撤离点)：\n")
for idx, step in enumerate(route):
# 检查是否收集物资
if step in items and step not in collected:
collected.append(step)
text = "收集到物资!"
elif map_grid[step[0]][step[1]] == 9:
text = "到达撤离点，完成任务!"
else:
text = ""
print(f"步骤{idx+1}: 位置{step} {text}")
print_map(map_grid, step, collected)
else:
print("找不到完整行动路径")