Домашно за група 3: Half-LIfe
Изисквания за завършване
Отворено: четвъртък, 25 март 2010, 00:00
До: събота, 10 април 2010, 01:00
"Окей, какво по дяволите става тука, какви са тия извънземни, майтапиш ли се с мене, къде съ-ъ-ъ-м?"
(В правоъгълен лабиринт с М реда и N колони, на позиция (X,Y), 1 <= X <= M, 1 <= Y <= N)
Извинете Гордън - той е моментно дезориентиран, защото в хороскопа му днес не пишеше, че ще се наложи да се бие с ордите от измерението Xen.
И на всичкото отгоре не е въоръжен! Ако някое извънземно го хване, свършен е!
(Има K на брой извънземни, като i-тото от тях е на позиция (X_i, Y_i), 1 <= X_i <= M, 1 <= Y_i <= N)
Вчера той беше ядрен физик от MIT.
Днес той е закуска за извънземни.
И е затворен в подземната лаборатория, която си е цял лабиринт.
Такъв е животът.
(L полета от лабиринта са непроходими, j-тото от тях е на позиция (X_j, Y_j), 1 <= X_j <= M, 1 <= Y_j <= N)
"Спокойно. Мисли, мисли Фриймън! Скоро ще дойдат военните. Те ще овладеят положението. Само трябва да ги дочакам и ще съм добре!"
Гордън много, много иска да дочака военните.
И би му било полезно да знае колко време най-много може да бяга от извънземните.
Движението се извършва по следния начин:
1) Гордън прави своя ход като или отива на свободна съседна клетка от лабиринта, или остава на място.
Две позиции са съседни ако имат обща страна.
2) Всяко от извънземните се придвижва по същия начин. Може да има по няколко извънземни на едно поле.
Вие трябва да му помогнете, като напишете програма, която казва колко хода най-много може да бяга Гордън
без значение как се движат извънземните!
Тоест, ако на ход T Гордън е на позиция (X_g, Y_g) и има поне един начин поне едно извънземно също да стигне до тази позиция в този момент или по-рано, то той бива изяден.
Вход:
на първия ред има четири числа: M, N, K, L
на втория ред има две числа - X, Y
на следващите K реда има по две числа - (X_i, Y_i) - координатите на всяко извънземно.
на следващите L реда има по две числа - (X_j, Y_j) - координатите на всяко непроходимо поле.
Изход:
едно цяло число - колко хода най-много може да бяга Гордън(т.е. на кой ход ще го хванат).
Пример:
6 5 2 5
4 3
1 1
6 2
2 2
2 3
2 4
5 3
5 4
Това отговаря на следния лабиринт:
(G е Гордън, A е извънземно, # е стена)
Решение:
6
Първите 3 хода са написани в лабиринта, а на ходове 4, 5 и 6 Гордън стои на едно място, чака и се моли.
А ако наистина искате да помогнете, напишете и маршрута по който трябва да се движи.
Всички решения, които правят това успешно, ще получат бонус изкривен метален лост(с който на края на семестъра можете да убедите асистента да ви пише още една единица към оценката).
(В правоъгълен лабиринт с М реда и N колони, на позиция (X,Y), 1 <= X <= M, 1 <= Y <= N)
Извинете Гордън - той е моментно дезориентиран, защото в хороскопа му днес не пишеше, че ще се наложи да се бие с ордите от измерението Xen.
И на всичкото отгоре не е въоръжен! Ако някое извънземно го хване, свършен е!
(Има K на брой извънземни, като i-тото от тях е на позиция (X_i, Y_i), 1 <= X_i <= M, 1 <= Y_i <= N)
Вчера той беше ядрен физик от MIT.
Днес той е закуска за извънземни.
И е затворен в подземната лаборатория, която си е цял лабиринт.
Такъв е животът.
(L полета от лабиринта са непроходими, j-тото от тях е на позиция (X_j, Y_j), 1 <= X_j <= M, 1 <= Y_j <= N)
"Спокойно. Мисли, мисли Фриймън! Скоро ще дойдат военните. Те ще овладеят положението. Само трябва да ги дочакам и ще съм добре!"
Гордън много, много иска да дочака военните.
И би му било полезно да знае колко време най-много може да бяга от извънземните.
Движението се извършва по следния начин:
1) Гордън прави своя ход като или отива на свободна съседна клетка от лабиринта, или остава на място.
Две позиции са съседни ако имат обща страна.
2) Всяко от извънземните се придвижва по същия начин. Може да има по няколко извънземни на едно поле.
Вие трябва да му помогнете, като напишете програма, която казва колко хода най-много може да бяга Гордън
без значение как се движат извънземните!
Тоест, ако на ход T Гордън е на позиция (X_g, Y_g) и има поне един начин поне едно извънземно също да стигне до тази позиция в този момент или по-рано, то той бива изяден.
Вход:
на първия ред има четири числа: M, N, K, L
на втория ред има две числа - X, Y
на следващите K реда има по две числа - (X_i, Y_i) - координатите на всяко извънземно.
на следващите L реда има по две числа - (X_j, Y_j) - координатите на всяко непроходимо поле.
Изход:
едно цяло число - колко хода най-много може да бяга Гордън(т.е. на кой ход ще го хванат).
Пример:
6 5 2 5
4 3
1 1
6 2
2 2
2 3
2 4
5 3
5 4
Това отговаря на следния лабиринт:
(G е Гордън, A е извънземно, # е стена)
A....
.###.
.....
..G..
..##.
.A...
Решение:
6
A....
.###.
..123
..G..
..##.
.A...
Първите 3 хода са написани в лабиринта, а на ходове 4, 5 и 6 Гордън стои на едно място, чака и се моли.
А ако наистина искате да помогнете, напишете и маршрута по който трябва да се движи.
Всички решения, които правят това успешно, ще получат бонус изкривен метален лост(с който на края на семестъра можете да убедите асистента да ви пише още една единица към оценката).