Задача №113348. Робот
Компания «Филипп индастриз» разрабатывает программу для нового робота-марсохода. Участок Марса, на котором будет работать робот, представляет собой квадратное поле размером \(n \times n\), разбитое на квадратные участки размером \(1 \times 1\), некоторые из которых могут содержать скалу \((1 \le n \le 1000\), не более 300 участков содержат скалу).
Введем на поле систему координат таким образом, что участки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), . . . ,(n, n)\). Программа для робота представляет собой последовательность инструкций, каждая из которых кодируется одной латинской буквой:
• «U» — переместиться с участка (x, y) на участок (x, y + 1).
• «D» — переместиться с участка (x, y) на участок (x, y − 1).
• «R» — переместиться с участка (x, y) на участок (x + 1, y).
• «L» — переместиться с участка (x, y) на участок (x − 1, y).
Для экономии инженеры записывают в память последовательность инструкций \(s\), пронумерованных от 1 до \(t\). Затем можно заставить робота выполнить подпрограмму — одну или несколько следующих подряд инструкций. Каждая подпрограмма, таким образом, характеризуется двумя целыми числами \((l, r)\) — номером первой и последней инструкции в подпрограмме.
В процессе лабораторного эксперимента робот был размещен на некотором участке тестового поля. Будем называть подпрограмму \((l, r)\) корректной, если при последовательном выполнении инструкций \(s[l], s[l + 1], \dots , s[r]\) робот не покидает поле и не перемещается на участок со скалой.
По описанию поля, программе для робота и его начальному положению определите, сколько у данной программы существует корректных подпрограмм.
В первой строке входного файла находятся два числа \(n\) и \(t\) (\(1 \le n \le 1000, 1 \le t \le 10^5\) ) — размер поля и количество инструкций в программе робота.
Во второй строке входного файла находится строка \(s\) длины \(t\) — программа робота. Гарантируется, что строка \(s\) состоит только из символов «U», «D», «R» и «L». Следующие \(n\) строк содержат по \(n\) символов в каждой и задают поле. Символ «.» означает, что участок пустой и по нему может перемещаться робот. Символ «#» означает, что на участке находится скала. Символ «@» означает, что в этой клетке находится стартовая позиция робота. Ось X направлена слева направо, ось Y — снизу вверх. Гарантируется, что символ «@» встречается ровно один раз, а символ «#» встречается не более 300 раз.
В единственной строке выходного файла выведите количество корректных подпрограмм.
В примере следующие подпрограммы являются корректными: (1, 1)=«U», (1, 2)=«UL», (1, 3)=«ULU», (3, 3)=«U», (3, 4)=«UR», (4, 4)=«R».
4 4 ULUR ..#. .... .#@. #.#.
6