@AlKp

Доброго времени суток, помогите пожалуйста разобраться с работой с трехмерными массивами.

Есть задачка: пятнашки, поле 3х3
1 8 4
6 7 3
0 2 5
Найти за какое наименьшее число ходов можно привести любое, рандомно перемешанное поле (например вверху) к эталону (внизу).
0 1 2
3 4 5
6 7 8
Нолик - пустая клетка, которая может меняться местами с соседними.

Что, собственно, я удумал:

Создаем переменную для количества шагов.
Создаем трехмерный массив (массив матриц), запихиваем туда наше перемешанное поле.
Создаем бесконечный цикл.
В нём, первым делом, проверяем все матрицы из трехмерного массива на соответствие эталону (при соответствии - выводим число шагов и выходим из цикла).
Дальше мы "делаем шаг" - меняем 0 местами с соседями и загоняем новую(ые) матрицы в трехмерный массив.
Делаем шаг+1.
Конец цикла.

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

Добавлено через 6 минут
Я думал, что проще всего сделать через вектор векторов векторов.
Но я не разбираюсь в работе с ним, как его заполнять и как в нем делать push_back() ?

0

@S_el

AlKp, а почему нельзя обойтись двумерным массивом(матрицей)?
P.S. Лучше попросите модератора перенести тему в алгоритмы.

0

@AlKp

А как обойтись двумерным массивом?
Я просто это представлял так.
У нас есть матрица:
1 8 4
6 7 3
0 2 5
Мы делаем все возможные шаги, и у нас уже 2 матрицы:
1 8 4 --- 1 8 4
6 7 3 --- 0 7 3
2 0 5 --- 6 2 5
На следующей итерации еще больше:
1 8 4 --- 1 8 4 --- 0 8 4 --- 1 8 4
6 0 3 --- 6 7 3 --- 1 7 3 --- 7 0 3
2 7 5 --- 2 5 0 --- 6 2 5 --- 6 2 5
И дальше их количество будет расти и нам надо их запоминать, чтоб потом делать новые шаги.

0

@S_el

А почему вы у меня об этом спрашиваете? Я когда в тему заходил,думал вопрос по C++ =)
Скорей всего здесь возможно более тонкое решение чем тупой перебор.

0

@nmcf

vector'ы вложенные используй для массива. Там поддерживается операция сравнения ==.

Добавлено через 1 минуту
Только тебе 4 измерения надо.

0

@AlKp

Спасибо, а почему 4 измерения и как его заполнять и как в нем делать push_back() ?

0

@nmcf

Ну первое измерение - шаг (уровень в дереве), второе - ход (на данном уровне), остальные - координаты.
Просмотр же будет параллельный, а не каждую ветвь в отдельности. Я правильно понимаю?
А что с push_back()? Будешь двумерными оперировать внутри.

Добавлено через 2 минуты
И сравнивать придётся не только с финальной расстановкой, но и со всеми промежуточными, чтобы исключить повторения, а то можно до бесконечности гонять этот ноль.

0

@takeneo

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

0

@nmcf

Нет, нужно хранить всю последовательность, иначе как узнать, какие ходы уже были?

0

@AlKp

Хорошо, а можете расписать как работать с трехмерным вектором, или дать ссылку на примеры? А то я вкурить не могу.

как теперь добавить еще одну матрицу 3х3 в конец?

0

@nmcf

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

1

@AlKp

Спасибо

0

@Mr.X

А почему одномерным нельзя-то, куда записать матрицу, прочитанную, например, по строкам?

0

@AlKp

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

0

@S_el

Можно и одномерным.Дело в алгоритме,а не представлении данных.

0