Задача 349
Муравей Лэнгтона

Муравей передвигается по правильному полю с квадратными клетками, окрашенными либо в черный, либо в белый цвет.
Муравей всегда смотрит в одном из основных направлений (влево, вправо, вверх или вниз) и передвигается на соседнюю клетку по одному из следующих правил:
- если он на черной клетке, то цвет клетки меняется на белый, муравей поворачивается на 90 градусов против часовой стрелки и передвигается прямо на следующую клетку.
- если он на белой клетке, то цвет клетки меняется на черный, муравей поворачивается на 90 градусов по часовой стрелке и передвигается прямо на следующую клетку.

Пусть изначально задано полностью белое поле из клеток. Сколько клеток окрасится в черный цвет после того, как муравей совершит 1018 переходов?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net