题解 | #矩阵中的路径#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
*/
func hasPath( matrix [][]byte ,  word string ) bool {
    // write code here
    // boundary condition
    if len(matrix[0]) == 0 {
        return false
    }

    // visited 数组标记是否已经访问过
    m, n := len(matrix), len(matrix[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    // 题目规定上下左右四个方向都可以移动，四个一维数组分别向左、右、上、下移动
    directions := [][]int{{-1,0}, {1, 0}, {0,1}, {0,-1}}
	
  	// 回溯
    var backtracking func(int, int, string) bool
    backtracking = func(i, j int, word string) bool {
        // trim tree 剪枝条件
        if matrix[i][j] != word[0] || visited[i][j] {
            return false
        }

        // condition for end recursion 终止条件
        if word = word[1:]; len(word) == 0 {
            return true
        }

        // access 访问该位置
        visited[i][j] = true
		
	  	// 从该位置出发尝试向左、右、上、下四个方向寻找下一个要匹配的字符
        for _, dir := range directions {
            x, y := i + dir[0], j + dir[1]
		  	// 不合法坐标判断
            if x < 0 || x >= m || y < 0 || y >= n {
                continue    
            }
			// 继续回溯，收集回溯结果，以便提前退出
            if backtracking(x, y, word) {
                return true
            }
        }
        // 当前位置出发的所有可能性都遍历完了，将其标记为 false，继续向上回溯；
	  	// 回溯处理过程都可以转换为一颗树，本题是四叉树；一般都是二叉树。
        visited[i][j] = false   
        return false
    }   
	
  	// 所有可能性
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == word[0] {
                if backtracking(i, j, word) { // 找到一个合法结果就返回
                    return true
                }
            }
        }
    }

    return false
}