1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// @Title: 矩阵中的路径 (矩阵中的路径  LCOF)
// @Author: 15816537946@163.com
// @Date: 2022-02-16 00:29:51
// @Runtime: 4 ms
// @Memory: 3.1 MB
func exist(board [][]byte, word string) bool {
    m,n := len(board), len(board[0])
    var dfs func(i,j,idx int) bool
    dfs = func(i,j,idx int) bool {
        if i <0 || i>=m || j<0 || j>=n || board[i][j] != word[idx] {
            return false
        }
        if idx == len(word)-1 {
            return true
        }
        board[i][j] = ' '
        res := dfs(i+1,j,idx+1) || dfs(i-1,j,idx+1) || dfs(i,j+1, idx+1) || dfs(i,j-1,idx+1)
        board[i][j] = word[idx]
        return res
    }

    for i := range  board {
        for j := range board[0] {
            if dfs(i,j,0) {
                return true
            }
        }
    }
    return false
}