题解 | #矩阵中的路径#

package main

func dfs(row int, col int, strlen int, i int, j int, count int, word string, matrix [][]byte, isVisited [][]bool) bool {
    if i < 0 || j < 0 || i >= row || j >= col || isVisited[i][j] || matrix[i][j] != word[count]{
        return false
    }
    if (count == strlen -1) {
        return true
    }
    isVisited[i][j] = true
    if dfs(row, col, strlen, i - 1, j, count + 1, word, matrix, isVisited) || dfs(row, col, strlen, i + 1, j, count + 1, word, matrix, isVisited) || dfs(row, col, strlen, i, j - 1, count + 1, word, matrix, isVisited) || dfs(row, col, strlen, i, j + 1, count + 1, word, matrix, isVisited) {
        return true
    }else { //回溯
        isVisited[i][j] = false 
        return false
    }
}

func hasPath(matrix [][]byte,  word string) bool {
    row := len(matrix)
    col := len(matrix[0])
    strlen := len(word)
    if row == 0 || strlen == 0 {
        return false
    }
    isVisited := make([][]bool, row)
    for k := 0; k < row; k ++ {
        isVisited[k] = make([]bool, col)
    }
    for i := 0; i < row; i ++ {
        for j := 0; j < col; j ++ {
            if matrix[i][j] == word[0] {
                if dfs(row, col, strlen, i, j, 0, word, matrix, isVisited) {
                    return true
                }
            }
        }
    }
    return false
}