求解一到算法题

[ljcarsenal]

输入:
输入第一行包含两个整数n、m(0<n, m<21)分别表示n行m列的矩阵，第二行是长度不超过100的单词W，从第3行到底n+3行是只包含大小写英文字母的长度为m的字符串。
如果能在地图中连成给定的单词，则输出“YES”，否则输出“NO”。注意：每个字母只能用一次。
只能上下左右行走

例如：
输入
5 5
SOLO
CPUCY
EKLQH
CRSOL
EKLQO
PGRBC
输出 yes

[bcxx]

三个方向的 KMP 啊……

[txx]

@bcxx kmp 干啥....21 这时间复杂度..bfs 就完了....

[c86jeff]

BFS吧

[monkeylyf]

先用给定的词做一个prefix tree
然后遍历每个点 对每个点做bfs 同时用prefix tree修枝

[ivanlw]

昨天大半夜刚做了这道题：
https://gist.github.com/ivanlw/9534435

[ivanlw]

@ivanlw 我用DFS，感觉思路比较自然一些，就是遍历和backtracking
不知道楼上说的BFS要怎么追溯判断到word的哪一步呢？在要queue里面压pair吗？

[txx]

@ivanlw bfs 最常见的地方就是走迷宫...走迷宫需要干的事情就是记住没一个节点是从哪里走过来的，别再走回去。这个一样啊，记录他走过的字符串就是了。

时间复杂度，极端情况下，即匹配串和字典全都是相同的字母例如a的矩阵和一个全都是a最后一个b的字符串，肯定要遍历全图
从矩阵的上的任意一点走遍全图是 20x20。然后要枚举每个点是20x20次，一共是20^4=160000。 远远小于 10^7可以在1s内出结果。

不过总觉得O(N^4)的时间复杂度 还是可以优化的。

[txx]

@ivanlw 时间复杂度的估算有点问题...没注意到字典是有长度的 100...那就是 O(100*n^2) 更小了.....

[ivanlw]

@txx
BFS更典型的场景应该是求无权图的最短路径吧；
DFS场景的是遇到whatever we're looking for的时候就可以返回了，也就是这题中的找到字符串就可以返回了，不一定要遍历地搜索完全图；所需要遍历的是尝试matrix中每个cell的值是否是字符串的第一个字符就行了（就是我exist函数的那个双层loop）

[ivanlw]

@txx 当然，记录走过了没……和BFS和DFS就没关系了，标记成其他值就行了，我一开始想错了

[txx]

@ivanlw bfs 也不用遍历完全啊 我说的是极端情况，你所说的无权图最短路径 不就是走迷宫么。。。迷宫是没有权的啊。当然有权的话 spfa 也是很不错的选择 还是基于bfs的 队列优化的bellman ford。。虽说不如堆优化的dijkstra 但刷题来说效果还是很让人满意的。扯远了

[bcxx]

咦，完全没看到数据规模这么小……

[Wins0n]

我也会用DFS

[wxstorm]

@txx 是O(M*N*W^3)

[txx]

@wxstorm 请教^3怎么出来的？

[wxstorm]

@txx 每一步最多三个方向。不能往回走。

[wxstorm]

@wxstorm 汗，说错了

[wxstorm]

@txx 说错了

[txx]

@wxstorm 你全走满了就是 M * N 啊....^3就不科学了吧...

[wxstorm]

@txx O（M*N*3^w)吧。
比如
aab
aaa
aaa

w=aaaaaaaac