题解 | #矩阵中的路径#

package main

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

	// flag 是否走过
	flag := make([][]bool, n)
	for i := range flag {
		flag[i] = make([]bool, m)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			// 每个位置都当作起点试一试
			if dfs(matrix, n, m, i, j, word, 0, flag) {
				return true
			}
		}
	}

	return false
}

// k 当前第几个字符
// 因为每一个点我们都可以往他的 4 个方向查找，所以我们可以把它想象为一棵 4 叉树，就是每个节点有 4 个子节点
func dfs(matrix [][]byte, n, m, i, j int, word string, k int, flag [][]bool) bool {
	if i < 0 || i >= n || j < 0 || j >= m {
		return false
	}

	if matrix[i][j] != word[k] {
		return false
	}

	if flag[i][j] {
		return false
	}

	if k == len(word)-1 {
		return true
	}

	flag[i][j] = true

	// up++
	if dfs(matrix, n, m, i-1, j, word, k+1, flag) {
		return true
	}
	// down++
	if dfs(matrix, n, m, i+1, j, word, k+1, flag) {
		return true
	}
	// l++
	if dfs(matrix, n, m, i, j-1, word, k+1, flag) {
		return true
	}
	// r++
	if dfs(matrix, n, m, i, j+1, word, k+1, flag) {
		return true
	}

	// 没找到经过此格的，修改回原来的样子
	flag[i][j] = false

	return false
}