Условие
Работа шамана тяжела и опасна. Ему ежедневно приходится наставлять и поддерживать людей, общаться с духами, брать на себя огромную ответственность за духовную и материальную жизнь племени. Естественно, от стресса у него появляются расстройства пищеварения, депрессия, проблемы со сном. Чтобы хоть как-то заснуть, шаман употребляет народные снотворные средства, обладающие побочными эффектами.
Например, во сне шаману привиделось, будто он оказался в ячейке четырехмерного куба, свернутого в четырехмерную же сферу. Как человек бывалый, шаман ничуть не растерялся и обнаружил за подкладкой кармана карту этого куба. На ней были помечены начальная ячейка (в которой он и находился) и ячейка с выходом из куба, а также для каждой ячейки куба было записано то время, за которое из нее можно перейти в соседнюю (не секрет, что в разных ячейках четырехмерных кубов время течет с разной скоростью).
Куб имеет размерность NxNxNxN, его ячейки определяются четырьмя координатами (x, y, z, w), причем каждая из них может принимать значения от 0 до N–1. Из любой ячейки можно перейти в восемь соседних за время, указанное для каждой из них на карте. Соседней будет та, у которой одна из координат отличается на 1, т.е., например, ячейка с координатами (x, y, z+1, w). Поясним свернутость куба в сферу на примере переходов из ячейки (0, 0, 0, 0). Если размерность куба больше 2, то возможны восемь различных переходов в ячейки: (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0), (0, 0, 0, N–1), (0, 0, N–1, 0), (0, N-1, 0, 0), (N-1, 0, 0, 0). При N=2 может быть всего четыре перехода, так как N–1=1. Таким образом, каждая координата берется по модулю N. Переход в любую из соседних ячеек занимает одинаковое время, указанное на карте для данной ячейки.
Поскольку у шамана еще много дел, то он хочет как можно быстрее добраться до выхода из куба.
Входные данные
Во входном файле записано целое число N (размер куба; 2 ≤ N ≤ 10). Далее идут два набора из четырех чисел — координаты начальной и конечной ячеек, а затем N4 целых чисел Mi (1 ≤ Mi ≤ 1000), описывающих карту. При этом индекс i = x•N3 + у•N2 + z•N + w; i изменяется последовательно от 0 до N4–1.
Пример входного файла
c.in
2
0 0 0 0
1 1 1 1
1 2 7 25 10 15 64 17 10 7 12 45 10 15 46 13
Выходные данные
В выходной файл выведите число K — минимальное время прохождения маршрута без учета последней ячейки.
Пример выходного файла
c.out
25
Решение
Главное при решении этой задачи — не пытаться представить себе четырехмерный куб, свернутый в сферу. Если вы не будете этого делать, то решите задачу очень просто. В частности, можно понять, что куб представляет собой ориентированный граф, причем из каждой его вершины исходит ровно восемь ребер одинакового веса (переходы в соседние ячейки куба).
Заведем два четырехмерных массива, описывающих карту куба, и массив, хранящий наименьшее время, за которое можно попасть в эту ячейку. Массив наименьших значений сначала заполним бесконечностями, за исключением начальной ячейки, куда запишем 0. Далее нужно считать карту куба. Она описывается в такой последовательности, что проще всего ее считать с помощью четырех вложенных циклов по индексам x, y, z, w. Затем следует воспользоваться стандартным алгоритмом Дейкстры, приспособленным для наших структур данных. В качестве пометки того, что кратчайшее расстояние до вершины уже посчитано, можно применить в карте отрицательное число.
Будем выполнять по одному шагу алгоритма Дейкстры до тех пор, пока конечная ячейка не будет помечена. На каждом шаге станем выбирать непомеченную вершину с минимальным временем (на первом шаге определится начальная вершина), пересчитывать минимальное время для восьми соседних вершин (одна из координат отличается на 1), если это необходимо (т.е. если минимальное время для соседней вершины больше, чем сумма минимального времени для обрабатываемой вершины и значение для нее на карте), а потом помечать эту вершину.
Свойство свернутости куба в сферу обрабатывается очень просто — к каждой изменяемой координате можно прибавлять N и затем брать остаток от деления на N.
Программно это решение легко записывается как небольшой листинг.
#include
#define MAX_N 10
#define INF 2000000000
int main(void)
{
int sx, sy, sz, sw, ex, ey, ez, ew, i, j, k, n, x, y, z, w, mx, my, mz, mw,
minval;
int t[MAX_N][MAX_N][MAX_N][MAX_N], mt[MAX_N][MAX_N][MAX_N][MAX_N];
freopen(“c.in“, “r“, stdin);
freopen(“c.out“, “w“, stdout);
scanf(“%d“, &n);
scanf(“%d%d%d%d“, &sx, &sy, &sz, &sw);
scanf(“%d%d%d%d“, &ex, &ey, &ez, &ew);
for (x=0; x
scanf(“%d“, &t[x][y][z][w]);
mt[x][y][z][w]=INF;
}
mt[sx][sy][sz][sw]=0;
while (t[ex][ey][ez][ew] != -1)
{
minval=INF;
for (x=0; x
{
minval=mt[x][y][z][w];
mx=x; my=y; mz=z; mw=w;
}
if (mt[(mx+1)%n][my][mz][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[(mx+1)%n][my][mz][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[(mx-1+n)%n][my][mz][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[(mx-1+n)%n][my][mz][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][(my+1)%n][mz][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][(my+1)%n][mz][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][(my-1+n)%n][mz][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][(my-1+n)%n][mz][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][my][(mz+1)%n][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][my][(mz+1)%n][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][my][(mz-1+n)%n][mw] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][my][(mz-1+n)%n][mw] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][my][mz][(mw+1)%n] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][my][mx][(mw+1)%n] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
if (mt[mx][my][mz][(mw-1+n)%n] > mt[mx][my][mz][mw] + t[mx][my][mz][mw])
mt[mx][my][mz][(mw-1+n)%n] = mt[mx][my][mz][mw] + t[mx][my][mz][mw];
t[mx][my][mz][mw]=-1;
}
printf(“%d“, mt[ex][ey][ez][ew]);
return 0;
}