Treasure Island

题意翻译

## 题目描述 我们勇敢的旅行者到达一个岛上，海盗在那里埋下了财宝。然而，当船即将停泊时，船长发现藏宝图被老鼠吃掉了一部分。 藏宝图可以表示为一个大小为$n\times m$的网格图。每个单元格代表地图上的一块正方形（正方形的边长等于一英里）。有些单元格代表海洋，它们是不可达的。所有其他单元格都是可达的，其中一些单元格有视野。 此外，地图还有一套共$k$个指令。每个指令的格式如下：“沿$y$方向走$n$英里” 可能的方向有：北、南、东和西。如果你仔细地遵循这些指示（你应该一个接一个地完成所有的指示），那么你应该准确地到达埋藏宝藏的地方。 不幸的是，船长不知道从哪个单元格开始执行指令，因为地图上的那一部分已经丢失了。但是船长很清楚地记得那个单元格有视野。另外，船长知道整个过程都经过岛上的可达单元格。 船长想知道哪些单元格值得一看。 ## 输入格式 第一行两个整数n,m 接下来n行，每行m个字符。“#”表示不可达单元格，“.”表示可达但没有视野的单元格，大写字母表示可达且有视野的单元格。 接下来一行，一个整数k。 接下来k行，每行一个字符dir,一个整数len，表示这条指令的内容为向dir方向走len步。“N”表示北，“S”表示南，“W”表示西，“E”表示东。定义向上为北。 ## 输出格式 一行若干个大写字母，表示可能作为起点的单元格。如果不存在，输出 "no solution"

题目描述

Our brave travelers reached an island where pirates had buried treasure. However as the ship was about to moor, the captain found out that some rat ate a piece of the treasure map. The treasure map can be represented as a rectangle $ n×m $ in size. Each cell stands for an islands' square (the square's side length equals to a mile). Some cells stand for the sea and they are impenetrable. All other cells are penetrable (i.e. available) and some of them contain local sights. For example, the large tree on the hills or the cave in the rocks. Besides, the map also has a set of $ k $ instructions. Each instruction is in the following form: "Walk $ n $ miles in the $ y $ direction" The possible directions are: north, south, east, and west. If you follow these instructions carefully (you should fulfill all of them, one by one) then you should reach exactly the place where treasures are buried. Unfortunately the captain doesn't know the place where to start fulfilling the instructions — as that very piece of the map was lost. But the captain very well remembers that the place contained some local sight. Besides, the captain knows that the whole way goes through the island's penetrable squares. The captain wants to know which sights are worth checking. He asks you to help him with that.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 3<=n,m<=1000 $ ). Then follow $ n $ lines containing $ m $ integers each — the island map's description. "\#" stands for the sea. It is guaranteed that all cells along the rectangle's perimeter are the sea. "." stands for a penetrable square without any sights and the sights are marked with uppercase Latin letters from "A" to "Z". Not all alphabet letters can be used. However, it is guaranteed that at least one of them is present on the map. All local sights are marked by different letters. The next line contains number $ k $ ( $ 1<=k<=10^{5} $ ), after which $ k $ lines follow. Each line describes an instruction. Each instruction possesses the form " $ dir $ $ len $ ", where $ dir $ stands for the direction and $ len $ stands for the length of the way to walk. $ dir $ can take values "N", "S", "W" and "E" for North, South, West and East correspondingly. At that, north is to the top, South is to the bottom, west is to the left and east is to the right. $ len $ is an integer from $ 1 $ to $ 1000 $ .

输出格式

Print all local sights that satisfy to the instructions as a string without any separators in the alphabetical order. If no sight fits, print "no solution" without the quotes.

输入输出样例

输入样例 #1

6 10
##########
#K#..#####
#.#..##.##
#..L.#...#
###D###A.#
##########
4
N 2
S 1
E 1
W 2

输出样例 #1

AD

输入样例 #2

3 4
####
#.A#
####
2
W 1
N 2

输出样例 #2

no solution