Автор: Кудинов Александр
Последняя модификация: 2007-03-19 21:07:12

Конкурс завершен.

Встречайте победителя!

Конкурсное задание

ВНИМАНИЕ!

В задании была обнаружена ошибка. Один из участников заметил
маленькую неточность в тестовом приложении.

Генерация координат городов выполняется следующим кодом:

for(int n = 0; n < cntCities; n++)
{
                cCity[n].x = rand() % 20;
                cCity[n].y = rand() % 20;
}

Здесь не отслеживается случай пространственного совпадения вновь
сгенерированного города с уже существующим. Это не верно, т.к.
координаты городов должны быть уникальны.

Предлагается заменить этот код на следующий:

for(int n = 0; n < cntCities; )
  {
                int x1, y1;
                x1 = rand() % 20;
                y1 = rand() % 20;
                if(!IsCityPoint(cCity, x1, y1))
                {
                        cCity[n].x = x1;
                        cCity[n].y = y1;
                        n++;
                }
  }

Извините за доставленные неудобства.

Скачать исходники

Рассмотрим абстрактную компьютерную игру. Это будет экономическая стратегия, в которой игроки должны развивать транспортную сеть. На игровом поле есть населенные пункты, между которыми надо перевозить пассажиров. Игроки строят здания вокзалов, соединяют их железнодорожным полотном и запускают по ним составы. В игре есть один игрок-человек и несколько игроков, которые управляются компьютером. По сценарию игры основные затраты участников связаны с прокладкой железных дорог между городами.

Наша задача написать кусочек «бота», который бы мог соперничать с игроком-человеком. Одним из компонентов компьютерного интеллекта (AI) является минимизация затрат на прокладку рельсов между городами. На начальном этапе игры компьютерные персонажи получают карту и строят план дорог между городами таким образом, чтобы затраты на реализацию этой сети были минимальны. Очевидно, что этого можно достичь, если суммарная длинна транспортной сети будет минимальна. В дальнейшем по мере продвижения по сценарию, наличию финансов и т.п. – компьютерные игроки будут прокладывать рельсы согласно заранее составленному плану. Боты также должны обеспечить максимальную широту охвата всех городов. Иными словами, все города должны быть соединены в единую сеть.

Карта игры имеет регулярную структуру. Т.е. состоит из клеточек, в каждой из которых может быть кусочек железной дороги. Город считается подключенным, если на его месте есть железнодорожное полотно. Координаты городов задаются отдельно от основной карты. Участок железной дороги, который помещается в клетку, имеет единичную длину. Игровой движок позволяет прогладывать рельсы только вертикально или горизонтально.

Ниже приведен один из вариантов оптимальной прокладки рельсов между 3 пунктами:

Суммарная длинна этой дороги 11 единиц – т.е. рельсы занимают 11 клеток. Буквой Х обозначены города. Рельсы внутри города также считаются за 1 ед. Расстояния между городами велики, поэтому их можно рассматривать как точку.

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

Теперь перейдем непосредственно к программной реализации.

Размер карты 20х20 клеток. На ней располагается 12 городов. Надо разработать Win32 DLL, которая имеет экспортируемую функцию со следующим прототипом:

extern "C" _declspec(dllexport) int CalcRailRoad(const struct CITY *pCities, TMap pMap);

pCities - указатель на массив из 12 элементов. Каждый элемент это структура, которая содержит координаты города.

pMap – это байтовый массив каждый элемент которого представляет клеточку на карте.

Структура с координатами имеет вид:

struct CITY
{
	int x;
	int y;
};

Карта:

typedef char TMap[sizeY][sizeX];			//sizeX == sizeY == 20

Доступ к карте осуществляется так:

pMap[y][x] = …;

Для прокладки участка железной дороги, надо записать по нужным координатам значение 0x01. Остальные значения будут приниматься за пустое место. На входе функции все элементы карты имеют значение 0x00 (пустое место).

Прототипы функции, а также объявленные константы располагаются в файле competition.h. Его можно найти в исходниках, которые прилагаются к данному заданию. В архиве также содержится тестовое приложение, которое рисует карту и проложенные дороги.

Условия победы:

1. Все города должны быть включены в транспортную сеть – обязательное условие.
2. Минимальная длина железнодорожной сети. Побеждает тот, у кого суммарная длина железнодорожных ветвей минимальная.
3. При прочих равных побеждает решение, которое имеет минимальный размер DLL.

Претенденты должны представить:

1. Скомпилированный DLL файл с именем sol.dll. Он будет использоваться для первичной проверки правильности решения. Также будет оцениваться размер именно этого файла.
2. Исходные коды на C++.
3. MS VC++ проект со всеми исходными файлами для ручной проверки правильности алгоритма.
4. Название и версия среды разработки которая использовалась для компиляции файла (см. п1). Если установлен Sevice Pack это необходимо указать.

В соответствие с правилами Вам надо отослать решение на e-mail competition@devdoc.ru до 15 марта 2007 года. Решение надо прицепить в виде аттача к письму. Для ускорения обработки, убедительная просьба упаковывать все файлы с помощью ZIP.

Если у Вас возникли какие-то вопросы по самому заданию или порядку проведения конкурса – обращайтесь competition@devdoc.ru.

Желаю всем удачи!

Коментарии к статье