скачать книгу бесплатно
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"
иначе
