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
```
1. `from collections import deque`: Импортируем deque для реализации очереди.
2. `def bfs(start, goals):`: Определяем функцию для поиска кратчайшего пути от `start` до ближайшей цели из `goals`.
3. `queue = deque([start])`: Инициализируем очередь с начальной позицией.
4. `visited = set()`: Создаем множество для отслеживания посещённых клеток.
5. `visited.add(start)`: Добавляем начальную позицию в множество посещённых.
6. `dist = {start: 0}`: Инициализируем словарь для хранения расстояний от начальной точки.
7. `while queue: …`: Запускаем цикл, пока есть элементы в очереди.
8. `x, y = queue.popleft()`: Извлекаем текущую позицию из очереди.
9. `if (x, y) in goals: …`: Если текущая позиция является целью, возвращаем расстояние и координаты.
10. `for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: …`: Перебираем все возможные направления движения (вверх, вниз, влево, вправо).
11. `nx, ny = x + dx, y + dy`: Вычисляем новые координаты.
12. `if is_valid(nx, ny) and (nx, ny) not in visited: …`: Если новые координаты валидны и не были посещены, добавляем их в очередь и множество посещённых, обновляем расстояние.
Основная логика движения и моделирования
Основной цикл для моделирования ходов
```python
for _ in range(K):
```
1. `for _ in range(K):`: Запускаем цикл для моделирования каждого хода.
Движение пастуха
```python
_, 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)
1. `_, nearest_sheep = bfs(pastukh, sheep_positions)`: Ищем ближайшую овцу для пастуха.
2. `if nearest_sheep: …`: Если найдена овца, определяем направление движения пастуха.
3. `px, py = pastukh`: Текущие координаты пастуха.
4. `sx, sy = nearest_sheep`: Координаты ближайшей овцы.
5. `if px < sx: px += 1 …`: Если пастух находится левее овцы, он движется вправо. Аналогично для других направлений.
6. `pastukh = (px, py)`: Обновляем координаты пастуха.
Движение волков
```python
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
1. `new_wolf_positions = []`: Создаем список для обновленных позиций волков.
2. `for wx, wy in wolf_positions: …`: Перебираем текущие позиции всех волков.
3. `_, target = bfs((wx, wy), sheep_positions + [pastukh])`: Ищем ближайшую цель (овца или пастух) для волка.
4. `if target: …`: Если найдена цель, определяем направление движения волка.
5. `tx, ty = target`: Координаты ближайшей цели.
6. `if wx < tx: wx += 1 …`: Если волк находится левее цели, он движется вправо. Аналогично для других направлений.
7. `new_wolf_positions.append((wx, wy))`: Добавляем обновленные координаты волка в список.
8. `wolf_positions = new_wolf_positions`: Обновляем позиции волков.
Обновление поля и проверка столкновений
```python
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'
1. `field = [['.' for _ in range(M)] for _ in range(N)]`: Пересоздаем поле, заполняя его пустыми клетками.
2. `field[pastukh[0]][pastukh[1]] = 'P'`: Обновляем позицию пастуха на поле.
3. `new_sheep_positions = []`: Создаем список для обновленных позиций овец.
4. `for x, y in sheep_positions: …`: Перебираем текущие позиции овец.
5. `if (x, y) not in wolf_positions: …`: Если овца не съедена волком, добавляем её в обновленное поле
В данной задаче была успешно смоделирована ситуация на лугу, где пастух старается спасти овец от волков. Мы рассмотрели основные этапы решения задачи, включая чтение входных данных, инициализацию игрового поля, реализацию вспомогательных функций для проверки валидности координат и поиска кратчайшего пути, а также логику движения пастуха и волков.
2. Пересечения кругов
Условие задачи: Даны координаты центров и радиусы двух кругов на плоскости. Необходимо определить, пересекаются ли эти круги.
Входные данные:
– Четыре вещественных числа: ( x_1, y_1, r_1, r_2 )
– ( x_1, y_1 ) – координаты центра первого круга.
– ( r_1 ) – радиус первого круга.
– ( x_2, y_2 ) – координаты центра второго круга.
– ( r_2 ) – радиус второго круга.
Выходные данные:
– Одно слово "YES", если круги пересекаются, и "NO" в противном случае.
Примеры:
