Дана квадратная игровая доска (массив) размера N×N для игры го, каждая позиция на которой либо пуста (0), либо занята чёрным камнем (1), либо занята белым камнем (2). Две позиции, соседние по вертикали или по горизонтали, считаются смежными. Множество пустых позиций, являющееся транзитивным замыканием отношения смежности, начиная с каждой позиции, принадлежащей этой группе (другими словами, компонента связности), называется пустой территорией. Если все позиции пустой территории являются смежными только друг с другом и с камнями только лишь одного цвета, то эта территория считается принадлежащей игроку соответствующего цвета.

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

Здравствуйте, nikov, Вы писали:

N>Дана квадратная игровая доска (массив) размера N×N для игры го, каждая позиция на которой либо пуста (0), либо занята чёрным камнем (1), либо занята белым камнем (2). Две позиции, соседние по вертикали или по горизонтали, считаются смежными. Множество пустых позиций, являющееся транзитивным замыканием отношения смежности, начиная с каждой позиции, принадлежащей этой группе (другими словами, компонента связности), называется пустой территорией. Если все позиции пустой территории являются смежными только друг с другом и с камнями только лишь одного цвета, то эта территория считается принадлежащей игроку соответствующего цвета.

N>Написать программу, которая для каждого из игроков подсчитывает общее количество позиций во всех территориях, принадлежащих этому игроку.

Будем красить нулевые позиции в разные оттенки чёрного цвета.
Если позиция соседствует слева и сверху с 1 — создаём новый чёрный цвет x (пусть они будут с нечётными номерами — т.е. 3, 5, и т.д.)
Если 1 и x — красим в цвет x.
Если x и x — тоже красим в x.
Если x и y — то считаем, что x и y эквивалентны, делаем себе пометку в специальной таблице; находим в ней самый минимальный цвет этого класса эквивалентности и красим в него.
Если 2 и x — опаньки, весь класс эквивалентности цвета x признаём как спорный; делаем себе пометку в таблице; красим в спорный цвет "-1".
То же, если x и y, где класс цвета y спорный.
Если 0 и 0 — ничего не делаем.

Одновременно и по той же схеме будем красить в новые белые цвета.

Всего достаточно 3 проходов:
1) красим слева-направо и сверху-вниз — заметём четверть доски — тень от фишек вправо и вниз до краёв
2) разворачиваем доску на 180°, повторяем покраску — заметём оставшуюся доску — тень от тени фишек
3) считаем покрашенные позиции чётных и нечётных цветов, проверяя, не входит ли каждая клетка в класс эквивалентности спорного цвета.

Нам понадобится N*N клеток, вмещающих числа от -1 до не более чем N*N; а также не более N*N-элементный N*N-ричный вектор для обслуживания классов эквивалентности.