SMART ANT

Задача Умный муравей.

Постановка задачи

Задано тороидальное поле(Уходя за край поля, муравей появляется с другого его края) n x n клеток, на нем заданным образом расположены k яблок. Необходимо построить конечный управляющий автомат Мили из l состояний, описывающий муравья, который за m ходов съедает все яблоки. Изначально муравей находится в верхней левой клетке тора и смотрит вправо. Муравей может видеть, есть ли яблоко в клетке перед ним, и на каждом шаге должен выполнять одно из трех действий:

1. повернуться на 90 градусов налево
2. повернуться на 90 градусов направо
3. переместиться на клетку вперед и съесть яблоко, если оно есть в клетке

Формат входной файла

В первой строке входного файла содержатся числа n l m, описание которых выше. Далее записаны n строк по n символов в каждой, которые описывают тор. Символ '*' соответствует наличию яблока, '.' - отсутствию. Должно быть гарантировано, что в левой верхней клетке тора нет яблока! Примеры входного файла можно посмотреть в папке './tests/'.

Формат выхода

В первой строке выводится имя файла, поданного на вход. Во второй строке выводится номер стартового состояния. В следующих l строках описываются состояния автомата в формате t0 t1 a0 a1, где t0 и a0 - номер состояния, в которое нужно перейти, если яблока перед муравьем нет, и действие, которое совершает муравей на данном переходе, а t1 и a1 - номер состояния, в которое нужно перейти, если перед муравьем есть яблоко, и действие, которое совершает муравей на данном переходе.

Installing:

mkdir Smart_Ant
cd Smart_Ant/
git clone https://github.com/kesarevs/smart_ant.git
cd smart_ant/c++
make

Usage:

./Smart_Ant.out

Использованая литература

1. http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf
2. http://rudocs.exdat.com/docs/index-229491.html