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

Автор:Н. Малявин, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
4 4
....
...#
*..*
..*.
DLDLUR
4 4
....
.#..
*..*
..*.
DLDRD
2
-1

0.062s 0.012s 15