1 (изменено: username_553380, 2018-04-15 01:32:49)

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

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

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

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

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

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

https://s14.postimg.cc/vnnr5wa81/surround-1.png   https://s14.postimg.cc/kbb5ocm69/surround-2.png

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

https://s14.postimg.cc/dkuof19c1/not-a-surround-1.png   https://s14.postimg.cc/iks4meu81/not-a-surround-2.png

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

https://s14.postimg.cc/nkpkugn0x/grounding.png

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

https://s14.postimg.cc/ub6241n35/grounding.png https://s14.postimg.cc/vq7msxvxt/failed-grounding.png

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

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

2

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

А разве углы между линиями останутся прямыми, если тор развернуть в плоскость? )