V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ljcarsenal
V2EX  ›  程序员

求解一到算法题

  •  
  •   ljcarsenal · 2014-03-14 00:33:47 +08:00 · 4232 次点击
    这是一个创建于 3909 天前的主题,其中的信息可能已经有所发展或是发生改变。
    输入:
    输入第一行包含两个整数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
    22 条回复    1970-01-01 08:00:00 +08:00
    bcxx
        1
    bcxx  
       2014-03-14 01:07:25 +08:00
    三个方向的 KMP 啊……
    txx
        2
    txx  
       2014-03-14 01:54:31 +08:00
    @bcxx kmp 干啥....21 这时间复杂度..bfs 就完了....
    c86jeff
        3
    c86jeff  
       2014-03-14 02:16:02 +08:00
    BFS吧
    monkeylyf
        4
    monkeylyf  
       2014-03-14 02:25:18 +08:00
    先用给定的词做一个prefix tree
    然后遍历每个点 对每个点做bfs 同时用prefix tree修枝
    ivanlw
        5
    ivanlw  
       2014-03-14 02:51:56 +08:00
    昨天大半夜刚做了这道题:
    https://gist.github.com/ivanlw/9534435
    ivanlw
        6
    ivanlw  
       2014-03-14 02:54:42 +08:00
    @ivanlw 我用DFS,感觉思路比较自然一些,就是遍历和backtracking
    不知道楼上说的BFS要怎么追溯判断到word的哪一步呢?在要queue里面压pair吗?
    txx
        7
    txx  
       2014-03-14 03:10:33 +08:00
    @ivanlw bfs 最常见的地方就是走迷宫...走迷宫需要干的事情就是记住没一个节点是从哪里走过来的,别再走回去。这个一样啊,记录他走过的字符串就是了。

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

    不过总觉得O(N^4)的时间复杂度 还是可以优化的。
    txx
        8
    txx  
       2014-03-14 03:12:22 +08:00
    @ivanlw 时间复杂度的估算有点问题...没注意到字典是有长度的 100...那就是 O(100*n^2) 更小了.....
    ivanlw
        9
    ivanlw  
       2014-03-14 04:09:48 +08:00
    @txx
    BFS更典型的场景应该是求无权图的最短路径吧;
    DFS场景的是遇到whatever we're looking for的时候就可以返回了,也就是这题中的找到字符串就可以返回了,不一定要遍历地搜索完全图;所需要遍历的是尝试matrix中每个cell的值是否是字符串的第一个字符就行了(就是我exist函数的那个双层loop)
    ivanlw
        10
    ivanlw  
       2014-03-14 04:11:51 +08:00
    @txx 当然,记录走过了没……和BFS和DFS就没关系了,标记成其他值就行了,我一开始想错了
    txx
        11
    txx  
       2014-03-14 04:47:39 +08:00 via iPhone
    @ivanlw bfs 也不用遍历完全啊 我说的是极端情况,你所说的无权图最短路径 不就是走迷宫么。。。迷宫是没有权的啊。当然有权的话 spfa 也是很不错的选择 还是基于bfs的 队列优化的bellman ford。。虽说不如堆优化的dijkstra 但刷题来说效果还是很让人满意的。扯远了
    bcxx
        12
    bcxx  
       2014-03-14 08:56:36 +08:00
    咦,完全没看到数据规模这么小……
    Wins0n
        13
    Wins0n  
       2014-03-14 09:15:55 +08:00
    我也会用DFS
    wxstorm
        14
    wxstorm  
       2014-03-14 11:15:50 +08:00
    @txx 是O(M*N*W^3)
    txx
        15
    txx  
       2014-03-14 11:58:32 +08:00
    @wxstorm 请教^3怎么出来的?
    wxstorm
        16
    wxstorm  
       2014-03-14 12:10:32 +08:00
    @txx 每一步最多三个方向。不能往回走。
    wxstorm
        17
    wxstorm  
       2014-03-14 12:12:59 +08:00
    @wxstorm 汗,说错了
    wxstorm
        18
    wxstorm  
       2014-03-14 12:13:16 +08:00
    @txx 说错了
    txx
        19
    txx  
       2014-03-14 12:13:45 +08:00
    @wxstorm 你全走满了就是 M * N 啊....^3就不科学了吧...
    wxstorm
        20
    wxstorm  
       2014-03-14 12:25:19 +08:00
    @txx O(M*N*3^w)吧。
    比如
    aab
    aaa
    aaa

    w=aaaaaaaac
    txx
        21
    txx  
       2014-03-14 12:31:17 +08:00
    @wxstorm 好吧...我疏忽了,谢谢。
    shenjiaqi
        22
    shenjiaqi  
       2014-03-14 12:56:31 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4921 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 10:00 · PVG 18:00 · LAX 02:00 · JFK 05:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.