题解 | #矩阵中的路径#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix char字符型二维数组
 * @param word string字符串
 * @return bool布尔型
 */
func hasPath(matrix [][]byte, word string) bool {
	// write code here
	var ans = false
  
	row := len(matrix)  // 矩阵的行数
	col := len(matrix[0]) // 列数
	end := len(word) - 1  // 搜索的字符数
  
    // 用来标记matrix[i][j] 是否已经走过
	visted := make([][]bool, row)
    for i := range visted {
        visted[i] = make([]bool, col)
    }
	
  	// 上下左右四个方向
	ways := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
	
  	//判断是否越界 
    var overBoard  func(i, j int) bool 
	overBoard = func(i, j int) bool {
		return i < 0 || i >= row || j < 0 || j >= col
	}
	// 搜索
	var dfs func(i, j, k int)
	dfs = func(i, j, k int) {
	  	// 退出条件
		if k > end || ans {
			return
		}
		// 如果搜到最后一个了，再上一层已经判断了字符的相等
	  	// 所以 ans 可以直接置为 true
		if k == end {
			ans = true
            return
		}

		// 继续搜
		for _, w := range ways {
            // 前后左右四个方向
			ni := i + w[0]
			nj := j + w[1]
		   // 下一个坐标如果越界则跳过
			if overBoard(ni, nj) {
				continue
			}
		  	// 判断下一个坐标等不等于下一个字符
			if matrix[ni][nj] != word[k+1] {
				continue
			}
			if visted[ni][nj] {
				continue
			}
		  	
			visted[ni][nj] = true
		  	// 继续搜下一个
			dfs(ni, nj, k+1)
			visted[ni][nj] = false
		}

	}

	out: for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
		    // 如果已经搜索到了，直接跳出循环
            if ans {
                break out
            }
			if matrix[i][j] == word[0] {
				visted[i][j] = true
				dfs(i, j, 0)
				visted[i][j] = false
			}
		}
	}
	return ans
}