Задача Z. Змейка и ягоды ≡

Условие

Дано поле, состоящее из W × H клеток. Каждая клетка поля либо пустая (обозначается символом '.', ASCII 46), либо содержит ягоду (обозначается символом '*', ASCII 42). Змейка располагается на поле, занимая последовательность клеток так, что каждая следующая клетка этой последовательности смежна по вертикали или горизонтали с предыдущей. Змейка выполняет последовательность шагов по следующим правилам:

• На каждый шаг задано направление движения; направление в следующий шаг времени смениться на прямо противоположное с предыдущим шагом.
• Голова змейки за шаг передвигается на одну клетку в заданном направлении. Остальные части змейки перемещаются каждая на клетку, которую занимала предыдущая часть.
• Если змейка попадает на клетку с ягодой то клетка становится пустой, и количество съеденных ягод увеличивается на единицу.
• После того, как змейка съедает ягоду, она вырастает на одну клетку — на следующий ход, сразу после того, как змейка закончит перемещение, у неё вырастает хвост. Эта новая её часть занимает предыдущую клетку старого хвоста.
• Если змейка выходит за поле или попадает головой на другую свою часть (т.е. самопересекается), игра заканчивается проигрышем.
• Изначально змейка занимает ровно одну клетку. На поле эта клетка обозначена символом '#', ASCII 35.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

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

Первая строка входного файла содержит целое число N — количество тестов в файле. Первая строка каждого теста содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание поля. Далее идёт строка S, каждый символ которой описывает направление движения змейки на очередном шаге:

• L — переместиться на одну клетку влево;
• R — переместиться на одну клетку вправо;
• U — переместиться на одну клетку вверх;
• D — переместиться на одну клетку вниз.

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

Выходной файл должен содержать N целых чисел, по одному на каждый тест: количество съеденных ягод, любо −1, если игра завершилась проигрышем.

Примеры тестов

2
4 4
....
...#
*..*
..*.
DLDLUR
4 4
....
.#..
*..*
..*.
DLDRD

2
-1