[ivank]

Какой структурой данных можно организовать хранение дерева? Глубина дерева не ограничена. Максимальное число ветвей на каждый узел - 4. »

Код:

struct Node {
    Node *children[4];
};

ня?

Дана матрица 10x10. Нужно обойти все элементы всеми возможными способами. Упростим задачу, предположив, что каждый узел можно посетить только один раз. Решение должно быть без рекурсии, и решение должно позволять возврат назад. »

Яндекс, друг молодёжи. Матрица - тот же граф, по сути. Вершины - клетки матрицы, рёбра - переходы по горизонтали/вертикали в соседние клетки. Без рекурсии не реализуется, можно обойтись банальным стеком, но по сути - та же рекурсия.

Как вариант другая задача, обойти матрицу 10x10, состоящую из 1 и 2, так чтобы не была посещена ни одна 1. Элемент можно посетить несколько раз. »

Те же яйца, вид сбоку. Вершины - клетки содержащие "2", рёбра - переходы в соседние двойки. Проблему составляет разрешение переходить назад. Вот такая матрица обычным поиском в глубину не обойдётся:

Код:

22222
21212

Для того, чтобы её обойти можно завести ещё одну матрицу - со счётчиком посещений вершины. И при очередном шаге поиска всегда идти в вершину с наименьшим числом посещений. В частности для матрицы приведённой выше, если мы начали путь в точке (2,1), то через 5 ходов матрица со счётчиками будет выглядеть так (соответственно находимся в точке (2,3)):

Код:

11100
10100

после этого, надо перейти в (1,3):

Код:

11200
10100

и в (2,3) на следующем шаге _не_ пойдём, т.к. там счётчик 1, а в (1,4) - пойдём, т.к. там ноль.

Можно доказать, что этот алгоритм всегда обходит все вершины, входящие в компоненту связности. Хотя, вероятно, и не самым оптимальным способом (не за минимальное число шагов).

В общем, читайте нормальный книжки по структурам данных и алгоритмам. Их много. Стандартные алгоритмы почти всегда можно адаптировать под свою задачу.