问题 J: 小新的字母广场

问题 J: 小新的字母广场

时间限制: 2 Sec  内存限制: 128 MB
提交: 201  解决: 36
[状态] [讨论版] [提交] [命题人:]
题目描述
       放假了,小新决定出去散散心,于是他来到了著名的字母广场。这个广场是由n*m块砖块铺成的,每个砖块上都有一个小写字母,所以叫字母广场。广场里好玩的东西太多了,小新刚喝完奶茶,就准备去广场的另一边去吃小吃。小新在走时,低头看了一眼广场地面上的字母,突然想到了一个问题。自己在移动过程中,会路过一些砖块,将这些砖块上的字母依次拼接在一起,可以得到一个字符串。
      小新移动的规则如下:
      小新可以在广场范围内移动,不能走出广场,小新的下一步可以选择向上、下、左、右中的任一方向移动一步。
      小新已经走过的砖块不能再次到达。
      小新落脚的位置一定是在砖块的中心,也就是说小新的一步不会踩到两块及以上的砖块。初始小新可以任意选择广场内的一块砖块作为出发点,在进行k(k>=0)步移动后,可以选择结束。
      小新在选择结束后,他走过的路径会形成一个字符串,小新想知道,他得到的字符串能否比目标字符串s小呢?
输入
输入第一行一个整数T(1<=T<=10),代表样例组数;
每组样例第一行两个整数n,m(1<=n,m<=1000),代表广场的大小。
接下来n行,每行m个小写字母,代表广场地面对应位置砖块上的字母。
所有样例n*m的和<=2e7.
接下来一行只包含小写字母的字符串s(1<=|s|<=100000)。

输出
对于每组样例,输出一行。如果小新可以走出一条比目标串s字典序更小的字符串,则输出“Yes”,否则输出“No”(不加引号)。
样例输入 Copy
2
3 3
abc
def
ghi
jklmnopqrstuvwxyz

2 3
uvw
xyz
abc
样例输出 Copy
Yes
No
提示
以下是百度百科对字典序的定义:
设想一本英语字典里的单词,何者在前何者在后?
显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列;如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。