Джеймс Дэвис – 40 задач на Python (страница 2)

# Инициализация поля

field = [['.' for _ in range(M)] for _ in range(N)]

field[pastukh[0]][pastukh[1]] = 'P'

for x, y in sheep_positions:

field[x][y] = 'S'

for x, y in wolf_positions:

field[x][y] = 'W'

# Вспомогательные функции

def is_valid(x, y):

return 0 <= x < N and 0 <= y < M

def bfs(start, goals):

queue = deque([start])

visited = set()

visited.add(start)

dist = {start: 0}

while queue:

x, y = queue.popleft()

if (x, y) in goals:

return dist[(x, y)], (x, y)

for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:

nx, ny = x + dx, y + dy

if is_valid(nx, ny) and (nx, ny) not in visited:

queue.append((nx, ny))

visited.add((nx, ny))

dist[(nx, ny)] = dist[(x, y)] + 1

return float('inf'), None

# Основная логика движения и моделирования

for _ in range(K):

# Движение пастуха

_, nearest_sheep = bfs(pastukh, sheep_positions)

if nearest_sheep:

px, py = pastukh

sx, sy = nearest_sheep

if px < sx: px += 1

elif px > sx: px -= 1

elif py < sy: py += 1

elif py > sy: py -= 1

pastukh = (px, py)

# Движение волков

new_wolf_positions = []

for wx, wy in wolf_positions:

_, target = bfs((wx, wy), sheep_positions + [pastukh])

if target:

tx, ty = target

if wx < tx: wx += 1

elif wx > tx: wx -= 1

elif wy < ty: wy += 1

elif wy > ty: wy -= 1

new_wolf_positions.append((wx, wy))

wolf_positions = new_wolf_positions

# Обновление поля и проверка столкновений

field = [['.' for _ in range(M)] for _ in range(N)]

field[pastukh[0]][pastukh[1]] = 'P'

new_sheep_positions = []

for x, y in sheep_positions:

if (x, y) not in wolf_positions:

field[x][y] = 'S'

new_sheep_positions.append((x, y))

sheep_positions = new_sheep_positions

for x, y in wolf_positions:

if field[x][y] == 'P':

field[x][y] = 'P'

else:

field[x][y] = 'W'

# Вывод результатов