Динамическое программирование в шаблонах

Есть такой чудный сайт выходного дня, как codeeval.com. На котором неплохая коллекция небольших алгоритмических задачек и удобная система проверки, позволяющая занимательно провести вечер скучающим программистам. Как правило в качестве входных данных используется файл с тестовыми данными. Однако мне попалась одна задача, в которой тестовые данные известны заранее. Загружать программу, которая будет просто выводить правильный ответ не спортивно, а вот вычислять его на этапе компиляции — самое то.

Что из этого получилось можно посмотреть внутри.

Задача сама по себе не сложная и рекурсивно решается очень просто. Например с помощью вот такой вот функции:

int GetRouteCount(int map, int x, int y) { 	if ((x == -1) || (y == -1) || (x == 4) || (y == 4)) return 0;  	if ((x == 3) && ( y == 3))  return 1;  	if ( ( map & (1 << ( ( x << 2) +y) )) != 0 ) return 0;  	map |= (1 << ( (x << 2) +y));  	return	GetRouteCount(map, x-1, y) + 			GetRouteCount(map, x+1, y) + 			GetRouteCount(map, x, y-1) + 			GetRouteCount(map, x, y+1); } 

И собственно получение результата:

int result = GetRouteCount(1, 0, 1) << 1; 

Теперь попробуем провернуть эти же вычисления в шаблонах. Как параметры шаблона нам надо передавать «карту» перемещений и координаты текущей точки. Так как вместо if будет использоваться специализация, то для проверки на посещение точки надо создать отдельный шаблон, у которого будет специализация на такой случай. Если попытаться добавить еще один параметр в основной шаблон, то возникнут неразрешимые ситуации на этапе компиляции. Выглядеть проверка на посещение будет вот так:

template< template<int, int, int> class _MR, int map, int x, int y, bool visited> struct GetCount { 	enum Result 	{ 		value =	_MR<(map | (1 << ( ( x << 2) +y ))), (x-1), y>::value + 				_MR<(map | (1 << ( ( x << 2) +y ))), (x+1), y>::value + 				_MR<(map | (1 << ( ( x << 2) +y ))), x, (y-1)>::value + 				_MR<(map | (1 << ( ( x << 2) +y ))), x, (y+1)>::value 	}; };  template< template<int, int, int> class _MR, int map, int x, int y> struct GetCount<_MR, map, x, y, true> { 	enum Result { value = 0 }; }; 

Теперь создадим основной шаблон, который будет иметь специализации по координатам, которые выходят за пределы сетки и проверяет, что достигнута точка назначения:

template <int map, int x, int y> struct MapRoute { 	enum Result { value = GetCount<MapRoute, map, x, y, ( (map & ( 1 << ( (x << 2) +y))) != 0 )>::value }; };  template<int map, int y> struct MapRoute<map, -1, y> { 	enum Result { value = 0 }; };  template<int map, int y> struct MapRoute<map, 4, y> { 	enum Result { value = 0 }; };  template<int map, int x> struct MapRoute<map, x, -1> { 	enum Result { value = 0 }; };  template<int map, int x> struct MapRoute<map, x, 4> { 	enum Result { value = 0 }; };  template<int map> struct MapRoute<map, 3, 3> { 	enum Result { value = 1 }; }; 

Вот и готово, получение результата выглядит почти так же лаконично, как и в варианте вычисления в рантайме:

int result = MapRoute<0, 0, 0>::value; 

Посмотреть весь код и результат его выполнения можно пройдя по ссылке.