Здравствуйте, olimp_20, Вы писали:

_>Входные данные
_>В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000.

Итого 150*150 клеток, т.е. 22.5 тысячи.
Помножить на 32 тысячи шагов волка — получается 72 миллиона.
Для моделирования "в лоб" не такая уж трудоёмкая задача. Вполне можно в 1с уложиться, наверно.

На каждом шаге, то есть, для момента времени t, получаем игровое поле, каждая клетка которой — это двоичный признак: "может ли здесь оказаться Красная Шапочка в этот момент времени".
Естественно, что для клеток, помеченных на карте как #, признак всегда "ложь".
И для двух клеток, в которых находился и будет находиться волк (поскольку они с КШ ходят по очереди), признак тоже всегда "ложь".
Шаг моделирования состоит в том, что клетка становится "истина" тогда и только тогда, когда
— она не помечена на карте как #
— в ней нет на предыдущем шаге и не будет на текущем волк
— в одной из соседних (смежных) клеток предыдущего шага была "истина"

Поскольку Шапочка на каждом ходу уходит с текущего положения, то клетка, бывшая "истиной", вполне может стать "ложью".
А поскольку Шапочка не ходит по диагонали, то соблюдается правило чётности. На чётных ходах истинными могут быть только "чёрные" клетки доски, а на нечётных — только "белые".
Это позволит вдвое сократить время работы.

Если по результатам моделирования клетка с бабушкой окажется помечена как "истина", то всё, приехали, ура.

Обычный клеточный автомат.
Не надо даже выстраивать очередь задач, как это делается в поиске в ширину на произвольных графах.

Здравствуйте, olimp_20, Вы писали:

_>Входные данные
_>В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000.

Итого 150*150 клеток, т.е. 22.5 тысячи.
Помножить на 32 тысячи шагов волка — получается 72 миллиона.
Для моделирования "в лоб" не такая уж трудоёмкая задача. Вполне можно в 1с уложиться, наверно.

На каждом шаге, то есть, для момента времени t, получаем игровое поле, каждая клетка которой — это двоичный признак: "может ли здесь оказаться Красная Шапочка в этот момент времени".
Естественно, что для клеток, помеченных на карте как #, признак всегда "ложь".
И для двух клеток, в которых находился и будет находиться волк (поскольку они с КШ ходят по очереди), признак тоже всегда "ложь".
Шаг моделирования состоит в том, что клетка становится "истина" тогда и только тогда, когда
— она не помечена на карте как #
— в ней нет на предыдущем шаге и не будет на текущем волк
— в одной из соседних (смежных) клеток предыдущего шага была "истина"

Поскольку Шапочка на каждом ходу уходит с текущего положения, то клетка, бывшая "истиной", вполне может стать "ложью".
А поскольку Шапочка не ходит по диагонали, то соблюдается правило чётности. На чётных ходах истинными могут быть только "чёрные" клетки доски, а на нечётных — только "белые".
Это позволит вдвое сократить время работы. (И вдвое сократить память, т.к. не нужно держать две доски для двух смежных шагов).

Если по результатам моделирования клетка с бабушкой окажется помечена как "истина", то всё, приехали, ура.

Обычный клеточный автомат.
Не надо даже выстраивать очередь задач, как это делается в поиске в ширину на произвольных графах. Практически, очередь полностью заполняется за 300 ходов, необходимых Шапочке добежать до любой точки доски.
Если есть желание, то можно первые 300 ходов делать с очередью, — а дальше чистый параллелизм и клеточный автомат.