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