题解 | #矩阵中的路径#

矩阵中的路径

https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6

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
}

全部评论

相关推荐

这不纯纯作弊了吗😢😢😢
编程界菜鸡:信这个的这辈子有了,这智商你靠啥都没用
你找工作的时候用AI吗?
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务