用 Go 剑指 Offer 12. 矩阵中的路径 （DFS + 回溯） - slowlydance2me
source link: https://www.cnblogs.com/slowlydance2me/p/17303475.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
用 Go 剑指 Offer 12. 矩阵中的路径 （DFS + 回溯）
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
dfs + 回溯 解法
wordb := []byte(word) // 转化一下 string 方便遍历
rows := len(board)
cols := len(board[0])
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if(dfs(board, wordb, i, j, 0)) { // 调用 dfs 函数
return true
}
}
}
return false
}
func dfs(board [][]byte, wordb []byte, i int, j int, k int) bool {
rows := len(board)
cols := len(board[0])
//先考虑 false 情况：越界、不相等、重复
if i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != wordb[k] {
return false
}
// 遍历完成返回true
if k == len(wordb) - 1 {
return true
}
//归零标记已遍历 byte 类型的0值为 0x0
board[i][j] = 0x0
//四个方向遍历
res := dfs(board, wordb, i + 1, j, k + 1) || dfs(board, wordb, i - 1, j , k + 1) || dfs(board, wordb, i, j + 1, k + 1) || dfs(board, wordb, i, j - 1, k + 1)
board[i][j] = wordb[k]
return res
}__EOF__
Recommend
-
59
题目 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
-
40
本文转自个人博客：CyC2018/CS-Notes 3. 数组中重复的数字 NowCoder 题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数
-
33
简介 最近在准备面试，发现一个不错的网站推荐给大家。也希望通过Go实现来把里面 剑指offer算法 。 如果觉得帮到了你，希望能为我点个赞呀。 如果发现代码有错，非常希望您能够在留言...
-
50
文章目录 41 和为S的连续正数序列 48 不用加减乘除做加法★ 49 把字符串转换成整数 欢迎关注个人数据结构专栏哈
-
26
这道题的一般解法是动态规划，优化时可以尝试找规律。 原题 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 ...
-
15
谈一谈你对BFC/IFC的理解「前端剑指offer」饥人谷若愚饥人谷前端，培养有灵魂的前端工程师
-
8
路径规划 | 图搜索算法：DFS、BFS、GBFS、Dijkstra、A*鬼木士不能遗臭万年，亦当流芳百世
-
11
HDU1045 Fire Net（DFS回溯）December 28, 2015题目链接 题意：给一个图，X 代表障碍物，问最多放置多少个 item，使每行每列的 item 间不能相互到达。 思路：八皇...
-
6
Armin's BlogPOJ1321 棋盘问题（DFS回溯）January 14, 2016题目链接 #include<iostream> #include<cmath> #include<cstring> #...
-
4
剑指 Offer 34. 二叉树中和为某一值的路径（java解题） 给你二叉树的根节点 root 和一个整数目标和 target...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK