Олимпиадный тренинг

Задача . Хождение за золотом - 3


Однажды царь решил вознаградить одного из своих мудрецов за хорошую работу. Он привел его в прямоугольную комнату размром NxM, в каждой клетке которой лежало несколько килограммов золота. Царь разрешил мудрецу сделать обойти несколько клеток (переходя с клетки, где сейчас находится мудрец, в одну из четырех с ней соседних), и собрать все золото, которое попадется на его пути.
Мудрецу разрешено более одного раза проходить по одной и той же клетке. Золото с нее он берет при этом  только один раз - когда проходит по клетке в первый раз.

Вам дан маршрут мудреца. Требуется определить, сколько килограммов золота он собрал.

Входные данные
Входные данные содержат план комнаты и маршрут мудреца. Сначала записано количество строк N, затем - количество столбцов M (1<=N<=20,1<=M<=20).
Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50).
Далее записано число X - сколько клеток обошел мудрец (1<=X<=10000).
Известно, что мудрец начал с клетки с координатами (1, 1). Далее записано X-1 число: куда перемещался мудрец:
  • число 1 обозначает, что мудрец делал шаг вправо,
  • число 2 обозначает, что мудрец делал шаг вверх,
  • число 3 обозначает, что мудрец делал шаг влево,
  • число 4 обозначает, что мудрец делал шаг вниз.
 
Известно, что мудрец не выходил из лабиринта, при этом он мог через одну и ту же клетку пройти несколько раз. 

Выходные данные
В выходной файл выведите количество килограммов золота, которое собрал мудрец.
 
Примеры
Входные данные Выходные данные
1
3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
4 1 1 2 3 3 1 4
24
 
 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6432
Python46
Комментарий учителя