обход матрицы инцидентности от -1 к 1

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

Начальная ячейка (5,1)


Может есть какой нибудь алгоритм?

Основная проблема в том, что в строке могут быть несколько -1 и 1. Как реализовать запоминание тех ячеек, которые уже обработаны, а которые еще нет?

>Основная проблема в том, что в строке могут быть несколько -1 и 1
если строки соответствуют дугам, то этого не может быть (у дуги одно начало, один конец, в остальных элементах строки нули)

собственно, сама задача - как мне кажется из условия - смахивает на нахождение Эйлерова цикла в графе (пройти по всем ребрам один раз, вершины могут повторяться). Хотя условие обхода всех ребер не озвучено...

да обходить все вершины не нужно
и все-таки мне кажется, что эйлеров цикл это нечто другое

А, когда писал прошлый пост, картинку не видел.
Здесь дуги по столбцам идут, а вершины по строкам.
Можно выполнять обход в ширину, пока не наткнемся на начальную ячейку. Таким образом будет найден кратчайший цикл.
При обходе ячейки помечаются, чтобы дважды не заходить

Цитата luna82 @ 14.10.09, 08:42

Основная проблема в том, что в строке могут быть несколько -1 и 1. Как реализовать запоминание тех ячеек, которые уже обработаны, а которые еще нет?

Прибавляй к значениям обработанных ячеек, скажем, 100. При необходимости снять отметку отнимешь 100 взад.

С пометкой вершин всё понятно теперь.
А как реализовать движение по графу?
И то что после -1 нужно искать 1, потом опять -1 и т.д.
Может сделать 2 процедуры для поиска по строкам и по столбцам и передавать значение ячейки, в которой в данный момент находимся...

Если находимся в ячейке с -1 - ищем в столбце +1, переходим туда. Больше ничего делать не надо, вариант однозначный.
Если в ячейке с +1 - перебираем все ячейки с -1 в данной строке.