Уведомления
Очистить все

Игра на тороидальном поле


dimin
Сообщения: 4
Topic starter
Присоединился: 8 месяцев назад

Сформулировать правила для игры на торе не сложно, но может быть не очевидно.

На всякий случай: тороидальное поле - это поле, у которого склеены противоположные края - левое с правым и верхнее с нижним.

Правила игры обычные, но с такими дополнениями:

0. Для окружения противника цепи можно строить через противоположные края.
1. Не все замкнутые цепи приводят к окружению, а только те, у которых ломанные непрерывно сжимаются в точку (в топологическом смысле).
2. Чтобы заземлиться, нужно прижать свои точки к своей несжимаемой замкнутой стенке.

Примеры: вот такими цепями можно окружать соперника:

Окружение-1 Окружение-2

А вот такими цепями окружать ничего нельзя:

Нет окружения-1 Нет окружения-2

Пример заземления: 

Заземление

Пример неправильного заземления:

Нет заземления-1 Нет заземления-2

Правило "окружаемости" можно переформулировать так: если точечное поле продолжить, скопировав это поле сверху, снизу, слева, справа от него и дальше до бесконечности, то области с конечной площадью являются допустимыми окружениями, а с бесконечной - недопустимыми.

В качестве простого, но не очень эффективного алгоритма проверки таких окружений могу предложить следующее:
Чтобы определить, находится ли какой-то пункт внутри окружения, начинаем с него делать обход с помощью BFS (DFS не подходит!). Когда обход пересекает границы поля, то обход продолжаем на копии поля (у которого своё множество visited пунктов). Если BFS доходит до изначального пункта на какой-то из копий, то окружения нет. Если BFS завершается, значит окружение есть.

Метки темы
Поделиться: