Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/word-search/description
: 79. Word Search
: 給你一個包含字母字元的matrix，求出是否可以找到目標字串word。
: 思路：
: 1.遍歷矩陣，如果board[i][j] = word[0] 則從這個點開始 DFS 搜索所有可能的走法，
:   如果可以走到底就返回 True。
: 2.標記原矩陣或用一個bool[][]紀錄走過的點避免重複走訪，遇到死路的時候把它復原。
: py code：
: ----------------------------------------
: class Solution:
:     def __init__(self):
:         self.dirs = [[1,0],[-1,0],[0,1],[0,-1]]
:     def exist(self, board: List[List[str]], word: str) -> bool:
:         m = len(board)
:         n = len(board[0])
:         for i in range(m):
:             for j in range(n):
:                 if board[i][j] != word[0]:
:                     continue
:                 # DFS
:                 if self.dfs(board, word, i, j, 0):
:                     return True
:         return False
:     def dfs(self, board: List[List[str]], word: str, y: int, x: int, idx:
: int):
:         m = len(board)
:         n = len(board[0])
:         if idx == len(word):
:             return True
:         if y < 0 or y == m or x < 0 or x == n:
:             return False
:         if board[y][x] != word[idx]:
:             return False
:         tmp = board[y][x]
:         board[y][x] = '*'
:         for dir in self.dirs:
:             new_y, new_x = y + dir[0], x + dir[1]
:             if self.dfs(board, word, new_y, new_x, idx + 1):
:                 return True
:         board[y][x] = tmp
:         return False
: ----------------------------------------

求救一下

照著溫莎思路寫了一下

但一直過不了

想問一下可能問題在哪

py code:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board[0])
        n = len(board)
        l = []
        visited = []
        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    l.append((i,j))


        def dfs(node,visited,c):
            visited.append(node)
            if board[node[0]][node[1]] == word[c]:
                c += 1
            if c == len(word):
                return True
            dx = [0,0,1,-1]
            dy = [1,-1,0,0]

            for i in range(4):
                x = node[0] + dx[i]
                y = node[1] + dy[i]

                if (x,y) in visited:
                    continue
                else:
                    if x>=0 and x<n and y>=0 and y<m:
                        if board[x][y] == word[c]:
                            return dfs((x,y),visited,c)

        for e in l:
            if dfs(e,visited,0) == True:
                return True
        return False

另外graph有沒有什麼解題技巧阿

寫了一個多禮拜還是不太懂怎麼解

感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.142.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712135915.A.049.html
推 JIWP: 你要用C寫
→ sustainer123: 我上次碰C都快半年前的事了
→ JIWP: 去問gpt
推 SecondRun: 大師
推 JIWP: 這題比較像backtracking吧
→ sustainer123: 真假 我思考一下 我以為是圖 我第一個想法是bfs
推 JIWP: 我不確定，我ME廢物，錯了不要找我
推 SecondRun: 我不懂py 不過m跟n有弄反嗎
→ sustainer123: 應該沒有 我前三筆有過 這邊出錯應該前三筆就掛了
推 JIWP: 你的visit有記得復原嗎？
→ sustainer123: 啊 感謝 忘了復原 我懂了