Фрактальный лабиринт
Нужно пройти по схеме от минуса к плюсу через квадраты с буквами, которые являются точной копией всего лабиринта.
Перерисовал схему в компасе.
Там проще рисовать.
Может кому поможет. ;-)
https://yadi.sk/d/RV7SnsRzkoUEx
раскрыть ветку (13)
раскрыть ветку (11)
Может быть массив, в котором элементы ноги квадратов, если там минус, то false, если плюс, то true.
Соединения прописать в алгоритме, который проходит по массиву и если находит значение, то присваивает его связанному элементу (то есть другому концу провода).
Если в момент присвоения обнаруживается, что значение уже есть и оно противоположно, то выход с выводом нужной цепочки, если нет, то каждым элементом массива становится ещё один массив, и итерация проходит уже по более глубокому пути.
Ну это догадка, программно ещё пока не знаю как решить.
раскрыть ветку (8)
раскрыть ветку (6)
Лучше в ширину искать, во-первых найденный путь будет кратчайшим, во-вторых не надо заморачиваться над бэктрэком, чтобы избегать зацикливания
раскрыть ветку (5)
раскрыть ветку (2)
раскрыть ветку (1)
Прям в точку) Я бы написал, если бы мне кто-нибудь этот граф в текстовый вид перевел. Но там столько много ребер, что заниматься этим никто не хочет.
С учетом того, что тут используются фрактальные схемы, я не вижу способа реализовать это в ширину.
раскрыть ветку (1)
Если видишь способ реализовать это в глубину, то автоматически есть способ реализовать это в ширину, всё это суть способ поиска на графе. Я тут только погорячился: бэктрэк нужен, хотя бы для того, чтобы не заходить в одни и те же схемы через одни и те же контакты, иначе ни DFS, ни BFS не смогут остановиться.
Можно представить себе, что помеченные буквами схемы это математические (чистые) функции, т.е. дёргая её за одну ниточку сколько угодно раз всегда будет тот же самый результат. Мне кажется, что здесь можно использовать модель циклического графа, алгоритм получится довольно простой, но нужно потратить кучу времени и нервных клеток на то чтобы эту лапшу из соединений перевести в форму графа
Ну да, просто как алгоритм более универсальней сделать, три прохода получится первым щаливаем известные выходы и входы ног - остаются константами для данной схемы далье метод условия, + условия
На ЯПлакал сидит взрослая аудитория, и там любят решать задачки) Возможно даже без срача в теме)