field[x][y] = 'S'
for x, y in wolf_positions:
field[x][y] = 'W'
1. `field = [['.' for _ in range(M)] for _ in range(N)]`: Создаем двумерный массив, представляющий луг, заполняя его пустыми клетками (`.`).
2. `field[pastukh[0]][pastukh[1]] = 'P'`: Размещаем пастуха на лугу в начальной позиции.
3. `for x, y in sheep_positions: field[x][y] = 'S'`: Размещаем овец на их начальных позициях.
4. `for x, y in wolf_positions: field[x][y] = 'W'`: Размещаем волков на их начальных позициях.
Вспомогательные функции
Проверка валидности координат
```python
def is_valid(x, y):
return 0 <= x < N and 0 <= y < M
```
1. `def is_valid(x, y): return 0 <= x < N and 0 <= y < M`: Функция проверяет, находятся ли координаты в пределах луга. Если координаты выходят за границы, возвращается False, иначе True.
Поиск кратчайшего пути (BFS)
```python
from collections import deque
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
```
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" в противном случае.
Примеры:
Пример 1:
Входные данные: 0 0 5 3 0 0 3
Выходные данные: YES
Пример 2:
Входные данные: 0 0 2 6 0 0 3
Выходные данные: NO
Решение: Для того чтобы определить, пересекаются ли два круга, можно воспользоваться следующими правилами:
1. Вычислим расстояние ( d ) между центрами кругов.
2. Если ( d ) меньше суммы радиусов ( r_1 ) и ( r_2 ) и больше разности радиусов ( |r_1 – r_2| ), то круги пересекаются.
3. Если ( d ) равно сумме радиусов, то круги касаются друг друга внешне.
4. Если ( d ) равно разности радиусов, то круги касаются друг друга внутренне.
5. Во всех других случаях круги не пересекаются.
Формула для вычисления расстояния между центрами кругов:
[ d = \sqrt{(x_2 – x_1)^2 + (y_2 – y_1)^2} \]
Псевдокод:
ввод x1, y1, r1, x2, y2, r2
вычислить d = sqrt((x2 – x1)^2 + (y2 – y1)^2)
если d <= r1 + r2 и d >= |r1 – r2| тогда
вывод "YES"
иначе
вывод "NO"
```
Псевдокод – это упрощенный язык описания алгоритмов, который используется для представления логики решения задачи без привязки к конкретному языку программирования. Он обычно используется для описания шагов алгоритма на естественном языке, что облегчает понимание и написание кода.
