1 Востаннє редагувалося Nekit (20.11.2018 19:27:45)

Тема: Задача з блоками (можна будь-якою мовою програмування)

Ми попали в Майнкрафтію, в якій все складається з блоків розміром 1*1*1.
Вся країна поділена на однакові чанки, по одному чанку для кожного жителя. Чанк представляє собою паралелепіпед розміром n*m*k блоків. Автор задачі живе в одному з таких чанків. Деякі блоки цього чанку пусті і через них можна пройти, а деякі заставлені каменем, тобто є непрохідними. Автор зараз знаходиться в блоці з координатами (1;1;1) і йому потрібно потрапити в блок з координатами (n;m;k).
Відповідно, ці два блоки завжди пусті. Автор може переходити в сусідній блок, якщо він пустий. Сусіднім вважається блок, який має спільну грань з даним, тобто знаходиться в одному з шести напрямків: знизу, зверху, зліва, справа, ззаду, спереду. Виходити за межі чанка заборонено законами Майнкрафтії.

Визначте, за яку найменшу кількість переходів автор може потрапити з блока з координатами (1;1;1) в блок з координатами (n;m;k).

Перший рядок містить 3 числа n, m, k (1≤n,m,k≤60) – розміри чанка.
В наступному рядку знаходиться n*m*k чисел, які описують чанк. Якщо певне число рівне одиниці, то відповідний блок пустий, інакше блок є непрохідним.
Номери блоків ідуть в наступному порядку:
(1;1;1),(2;1;1),(3;1;1)...(n;1;1), (1;2;1), (2;2;1)...(n;m;1), (1;1;2), (2;1;2)... (n-1;m;k), (n;m;k).

Виведіть найменшу кількість переходів, необхідну для того, щоб потрапити з блока з координатами (1;1;1) в блок з координатами (n;m;k).
Гарантується, що завжди можна дістатися з початкового в кінцевий блок.

Вихідні дані в форматі input.txt :
2 3 2
0 1 1 1 0 1 0 0 1 0 1 0

Результат роботи в файлі output.txt :
4

В першому прикладі автор може рухатися наступним маршрутом: (1;1;1), (1;1;2), (2;1;2), (2;2;2), (2;3;2)

2

Re: Задача з блоками (можна будь-якою мовою програмування)

Знову горе-олімпіадник
Давайте ви вирішите цю (дуже класичну) задачу в двох вимірах, а потім подумаємо як для 3 зробити?

Подякували: leofun011

3

Re: Задача з блоками (можна будь-якою мовою програмування)

ну, те що пам'ятаю з універу: то для 2д можна заюзати ж графи. Можна пригадати, як саме. А що робити з 3д?

4 Востаннє редагувалося koala (21.11.2018 12:59:48)

Re: Задача з блоками (можна будь-якою мовою програмування)

Та ну, просте узагальнення хвильового алгоритму, причому без зворотнього руху.
Q-bart, а яка різниця - 2D чи 3D для графів? Ну, сусідів більше. І все.

Подякували: leofun01, Chemist-i, 0x9111A, Q-bart4

5 Востаннє редагувалося Q-bart (21.11.2018 13:14:42)

Re: Задача з блоками (можна будь-якою мовою програмування)

ї**на, система 1 мого мозку. Це було просто додуматись, що повністю той самий алгоритм