Архив форумов ЦИТФорума

[alesha]

Задача.
Есть двумерный массив MAS[100][100];
Изначально он заполнен значением "-1"
Затем в него произвольным образо записывают N - значений отличных от "-1". И задают клетку со значенем "-1".
Требуется начиная с заданной клетки построить замкнутый контур таким образом, чтобы в вершинах контура были значения "-1"
И в контуре была только одна клетка со значенем "-1" - начальная.
Двигаться можно только ходом шахматной ладьи, проходить можно через любые клетки, даже со значением не "-1", главное повороты делать в клетках отличных от "-1".
Пример контура.
X - начальная клктка
* - путь
U - вершины контура
U*******************U
* *
* *
* *
U*******X********************U
* *
* *
* *
U*******U

[DmitryShm]

Стром граф по правилу: вершинами будут начальная "-1" и остальные "не -1". 2 вершины инциндентны ребру тогда и только тогда, когда из одной в другую можно пройти ходом ладьи. Тогда задача сводится к нахождению замкнутого пути в графе (советую пользоваться динамическим массивом и отсечениями ввиду размеров массива, эвристики тоже не помешают , поиск вглубину или волной..). Если что, прочитайте любую книжку, в которой как-то освещаются базовые алгоритмы.
_________________
love IT