Квест для программистов
Добавлено: Вт окт 06, 2009 11:43 pm
Нужно написать алгоритм, который бы рисовал карту зоны. Есть массив комнат с выходами, каждой комнате нужно назначить целочисленные координаты.
Предполагается, что получающийся граф - планарный; если граф не планарный, то желательно, чтобы было минимальное количество пересечений ребер.
Также для упрощения можно считать, что выходов всего 4 (nesw).
Выходы в exits нумеруются north, east, south, west, up, down.
Исходно дан массив Room* rooms[N], нужно назначить всем комнатам координаты x, y, z.
Нужно, чтобы алгоритм корректно работал в подобных случаях:
Ожидается код на c/c++. Результаты можно слать на admin@c7i.ru.
Написавшему - приятная плюшка.
Предполагается, что получающийся граф - планарный; если граф не планарный, то желательно, чтобы было минимальное количество пересечений ребер.
Также для упрощения можно считать, что выходов всего 4 (nesw).
Код: Выделить всё
class Door
{
public:
Room *getRoom() const;
bool isOneside() const;
};
struct Room
{
struct Exit
{
Door *door;
Exit() : door(0) {}
};
Exit exits[6];
int x, y, z;
};
Исходно дан массив Room* rooms[N], нужно назначить всем комнатам координаты x, y, z.
Нужно, чтобы алгоритм корректно работал в подобных случаях:
Код: Выделить всё
*---*---*---*
| |
| *
|
*---*---*---*
*---*---*---*
| |
*---*-------*
Написавшему - приятная плюшка.
