Лимит времени 1с.
Красная Шапочка спешит навестить свою больную бабушку и отнести ей лекарства и еду. Ее путь лежит через густой лес, который разбит на квадраты. С квадрата в квадрат можно попасть только двигаясь вверх, вниз, влево или вправо. За пределы леса выходить нельзя, лес окружен непроходимым болотом. Лес имеет форму прямоугольника в котором N строк и M столбцов. Красная Шапочка живет в левом верхнем углу этого леса, а ее бабушка — в правом нижнем. Дом бабушки охраняют охотники. Тем лесом бродит Серый Волк, которого очень надо остерегаться Красной Шапочке. К счастью, исходное положение и маршрут его ей известны.
За какую наименьшее количество шагов Красная Шапочка может достичь своей цели, соблюдая при движении такие правила (шаг — это перемещение из клетки в соседнюю клетку):
1. Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку.
2. Перемещение осуществляется поочередно: сначала Серый Волк, потом Красная Шапочка.
3. Не допускается нахождение в одном квадрате Красной шапочки и Серого Волка.
4. Ходы Красной шапочки и Серого Волка обязательны.
5. Если ходы Серого Волка закончились, то он остается в последней достигнутой клетке. Но заранее известно, что он при этом не заблокирует путь Красной Шапочки к бабушке. Если Серый Волк достиг финиша (квадрата в котором живет бабушка), то его убивают охотники.
Входные данные
В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000.
Исходные данные
Единственное число — минимальное число шагов, необходимое для достижения финиша.

3 5
.....
.#...
...#.
1 2
RRLDRRD

Ответ: 8

Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с.

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

_>Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с.

Берем граф, в котором каждой вершине приписываем 3 координаты. 2 из них — координаты квадрата, еще одна — номер шага. И используем ПВШ. Строить весь граф не нужно, достаточно уметь перебирать исходящие ребра из данной вершины. Третья координата всегда меняется t -> t+1. Останавливаемся в вершине вида (N, M, x).

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

_> Действительно ли КШ может быть такой интеллектуальной в этой задаче?

Обязана быть. Например, если Волк стартует из (1,3) и двигается по маршруту L,D,D,D,D...,U,U,U...,D,D... (бегает по 2-му столбцу вверх-вниз), то Шапке придется где-то сходить обратно вверх.

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


S>Берем граф, в котором каждой вершине приписываем 3 координаты. 2 из них — координаты квадрата, еще одна — номер шага. И используем ПВШ. Строить весь граф не нужно, достаточно уметь перебирать исходящие ребра из данной вершины. Третья координата всегда меняется t -> t+1. Останавливаемся в вершине вида (N, M, x).

Если я правильно понял, то ПВШ — поиск в ширину.
Каждая новая волна во время поиска в ширину движется к еще не посещенным вершинам графа. Если КШ придется отходить, то получится цикл. Возникает вопрос: как вовремя выходить из цикла, чьобы продолжить движение? И как искать правильно направление, если придется идти через уже посещенные вершины?

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

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

_>> Действительно ли КШ может быть такой интеллектуальной в этой задаче?

L>Обязана быть. Например, если Волк стартует из (1,3) и двигается по маршруту L,D,D,D,D...,U,U,U...,D,D... (бегает по 2-му столбцу вверх-вниз), то Шапке придется где-то сходить обратно вверх.

Заметим, что если ширина и длинна леса больше 2, то КШ достаточно не более чем одного "шага назад".

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

_>Если я правильно понял, то ПВШ — поиск в ширину.
_>Каждая новая волна во время поиска в ширину движется к еще не посещенным вершинам графа. Если КШ придется отходить, то получится цикл. Возникает вопрос: как вовремя выходить из цикла, чьобы продолжить движение? И как искать правильно направление, если придется идти через уже посещенные вершины?

Лишь 2 из 3х координат вершины могут иметь повтор. А координата-номер шага каждый раз новая. Так что, цикл исключен.
Искать направление не нужно, ПВШ все разрулит с точностью до эквивалентных по числу шагов путей.

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

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

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

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

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

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

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

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


К>Поскольку Шапочка на каждом ходу уходит с текущего положения...

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

 0    1   1   1
0x0  0x0 0x2 4x2
 0    0   3   3

"х" — текущее положение Шапочки, 1,2,3,4 — шаг на котором была посещена позиция.

Куда именно уходит Шапочка в клеточном автомате? В "поиске в ширину" новый ход выполняется в непосещенные позиции, а в клеточном автомате на каждом этапе все допустимые позиции как бы становятся снова непосещенными? То есть вопрос: как контролировать движение Шапочки, чтобы она "не забывала" двигаться к бабушке (на финиш)?

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

_>

_> 0    1   1   1
_>0x0  0x0 0x2 4x2
_> 0    0   3   3
_>

_>"х" — текущее положение Шапочки, 1,2,3,4 — шаг на котором была посещена позиция.

_>Куда именно уходит Шапочка в клеточном автомате? В "поиске в ширину" новый ход выполняется в непосещенные позиции, а в клеточном автомате на каждом этапе все допустимые позиции как бы становятся снова непосещенными? То есть вопрос: как контролировать движение Шапочки, чтобы она "не забывала" двигаться к бабушке (на финиш)?

Клеточный автомат — это Красная Шапочка Шрёдингера. Он показывает суперпозицию всех возможных положений Шапочки в данный момент времени.
"Двигаться на финиш" — это оптимизация и эвристика, построить конус пространства-времени, и экономить на вычислениях за пределами конуса.
Потому что понятно, что первые N шагов Шапочка не может оказаться на расстоянии более N от старта.
Но с учётом того, что траектории Волка занимают до 32 тысяч, то это грошовая экономия.

    +W...  + шапочка, W волк, # стена, F финиш (бабушка)
    .#...
    ...#F

шаг 1
  волк ходит вправо
    +.W..
    .#...
    ...#F

  шапочка ходит во все стороны
    .+W..
    +#...
    ...#F

шаг 2
  волк ходит вправо
    .+.W.
    +#...
    ...#F

  шапочки ходят во все стороны (в т.ч. на старт)
    +.+W.
    .#...
    +..#F

шаг 3
  волк ходит влево и съедает одну из шапочек
    +.W..
    .#...
    +..#F

  остальные шапочки ходят во все стороны
    .+W..
    +#...
    .+.#F

шаг 4
  волк ходит вниз
    .+...
    +#W..
    .+.#F

  шапочки ходят во все стороны
    +.+..
    .#W..
    +.+#F

шаг 5
  волк ходит вправо
    +.+..
    .#.W.
    +.+#F

  шапочки ходят во все стороны
    .+.+.
    +#+W.
    .+.#F

шаг 6
  волк ходит вправо
    .+.+.
    +#+.W
    .+.#F

  шапочки ходят во все стороны
    +.+.+
    .#.+W
    +.+#F

шаг 7
  волк ходит вниз и его съедает бабушка
    +.+.+
    .#.+.
    +.+#F

  шапочки ходят во все стороны
    .+.+.
    +#+.+
    .+.#F

шаг 8
  волк никуда не ходит

  шапочки ходят во все стороны, и одна из них съедает бабушку
    +.+.+
    .#.+.
    +.+#+

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

	Скрытый текст
	_>Лимит времени 1с. _>Красная Шапочка спешит навестить свою больную бабушку и отнести ей лекарства и еду. Ее путь лежит через густой лес, который разбит на квадраты. С квадрата в квадрат можно попасть только двигаясь вверх, вниз, влево или вправо. За пределы леса выходить нельзя, лес окружен непроходимым болотом. Лес имеет форму прямоугольника в котором N строк и M столбцов. Красная Шапочка живет в левом верхнем углу этого леса, а ее бабушка — в правом нижнем. Дом бабушки охраняют охотники. Тем лесом бродит Серый Волк, которого очень надо остерегаться Красной Шапочке. К счастью, исходное положение и маршрут его ей известны. _>За какую наименьшее количество шагов Красная Шапочка может достичь своей цели, соблюдая при движении такие правила (шаг — это перемещение из клетки в соседнюю клетку): _>1. Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку. _>2. Перемещение осуществляется поочередно: сначала Серый Волк, потом Красная Шапочка. _>3. Не допускается нахождение в одном квадрате Красной шапочки и Серого Волка. _>4. Ходы Красной шапочки и Серого Волка обязательны. _>5. Если ходы Серого Волка закончились, то он остается в последней достигнутой клетке. Но заранее известно, что он при этом не заблокирует путь Красной Шапочки к бабушке. Если Серый Волк достиг финиша (квадрата в котором живет бабушка), то его убивают охотники. _>Входные данные _>В первой строке размер поля: два числа через пробел 0<N, M≤150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) — Клетка свободна. Решетка (#) — непроходимая клетка. В следующей строке два числа — номер строки и столбца, где изначально находится Серый Волк. Далее идет строка с описанием пути Серого Волка: R — движение вправо, L — влево, U — вверх, D — вниз. Количество ходов соперника не более 32000. _>Исходные данные _>Единственное число — минимальное число шагов, необходимое для достижения финиша. _> _>3 5 _>..... _>.#... _>...#. _>1 2 _>RRLDRRD _>Ответ: 8 _> _>Как мене представляется — тут можно использовать волновой алгоритм (обход в ширину) Правда возникает тревожное ощущение, что условию задачи может соответствовать ситуация: КШ видит, что столкнется с СВ, отступает на несколько шагов, пропуская волка, а потом двигается дальше. Действительно ли КШ может быть такой интеллектуальной в этой задаче? Если да, то в чем состоит модификация волнового алгоритма? Или тут нужен совсем другой подход? Выполнение программы — 1с.

Опишу, как я ее решил.
Моё решение скорей всего чем-то похоже на приведенные выше.
На первом шаге есть начальная координата красной шапочки (далее КШ) и она может посетить некоторые соседние клетки. Заполняем множество (хэш-таблица или битовый массив) клеток, куда она может пойти.
На каждом следующем шаге перебираем множество клеток предыдущего шага и строим новое множество клеток, куда она может пойти из каждой из них. При этих переходах учитывается позиция волка (начальная и конечная — для 2 соседних шагов) — клетка с волком занята.
Каждый новый шаг — каждое новое множество клеток.
Как только среди этих клеток появится клетка бабушки — финиш.
Поскольку в условии сказано, что КШ гарантированно придет к бабушке, отслеживать бесконечное блуждание не надо (если б надо было — как вариант еще можно хранить карту слепков текущего множества клеток — то есть на каждом шаге из множества клеток строим некоторый слепок/хэш и помещаем его в отдельную карту, заполнять эту карту начинаем только после остановки волка).
Попробуем оценить время.
Вначале кол-во клеток будет расти квадратично от кол-ва шагов, далее довольно быстро оно насытится и будет примерно постоянным, не больше N*M.
Время расчета перехода на следующую клетку это О(1) для каждой клетки, т.е. для всех клеток на каждом шаге — О(N*M).
Если кол-во ходов обозначить за Х, то полное время О(N*M*Х).
150*150*32000 = 720.000.000
Можно на сильном железе вытянуть за секунду столько?
Например, бабушка будет жить среди плотной застройки деревьев, и волк её будет 31999 ходов охранять, не давая пройти.
Если нельзя — будем оптимизировать. ))

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

L>>Обязана быть. Например, если Волк стартует из (1,3) и двигается по маршруту L,D,D,D,D...,U,U,U...,D,D... (бегает по 2-му столбцу вверх-вниз), то Шапке придется где-то сходить обратно вверх.

C>Заметим, что если ширина и длинна леса больше 2, то КШ достаточно не более чем одного "шага назад".

Например, бабушка живет среди плотной "застройки" деревьев, и волк её 31999 ходов охраняет, не давая пройти.
И Шапке придется много и долго гулять, прежде чем навестить бабушку. Будет она ходить вперед-назад, или вправо-влево, или по кругу, или по восьмерке — это её дело.
Но "шагов назад" ей придется совершить много. ))

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

_>150*150*32000 = 720.000.000
_>Можно на сильном железе вытянуть за секунду столько?

Легко.

1. Как я уже сказал, из-за чётности можно обойтись единственным игровым полем.
2. Шапочки ходят
— ниоткуда: row[y] &= ((tact ^ y) % 1) ? even_row_mask : odd_row_mask
— вверх: row[y] |= row[y+1]
— вниз: row[y] |= row[y-1]
— влево: row[y] |= row[y]<<1
— вправо: row[y] |= row[y]>>1
3. Протравливаем шапочек деревьями
— row[y] &= nontrees[y]
4. Протравливаем шапочек волком
— row[wolf_y] &= wolf_row_mask

Для удобства можно окружить периметр леса плотной стеной деревьев, чтобы не заниматься ветвлениями на границах.
Поскольку длина битового вектора не более 150, нам вполне хватит одного 256-битного регистра (AVX) или даже 4 обычных 64-битных.
И в кеш это отлично влезает, и параллелится при желании.

http://ideone.com/zfV4eJ — тупой бенчмарк. 32000 тактов за 70 миллисекунд.