这篇文章将为大家详细讲解有关golang刷leetcode 技巧之如何解决矩阵中的路径问题，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
创新互联服务项目包括偏关网站建设、偏关网站制作、偏关网页制作以及偏关网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，偏关网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到偏关省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：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
提示：
解题思路
1，深度优先遍历
2，首字母不匹配可以剪枝
3，注意golang slice 数据地址一样，所以，需要clone 路径，否则会回溯失败
测试用例
[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"
[["a","b"]]
"ba"
[["a"]]
"a"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"
代码实现
func exist(board [][]byte, word string) bool { for i:=0;i for j:=0;j if board[i][j]!=word[0]{ continue } mark:=getMark(board) if dfs(board,mark,i,j,word){ return true } //fmt.Println(mark) } } return false}
func dfs(board [][]byte,mark1 [][]int,i,j int,word string)bool{ if word=="" { return true } if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || board[i][j]!=word[0] || mark1[i][j]!=0{ return false }
if len(word)==1 && word[0]==board[i][j]{ return true } mark:=cloneMark(mark1) mark[i][j]=1 return dfs(board,mark,i+1,j,word[1:]) || dfs(board,mark,i,j+1,word[1:]) || dfs(board,mark,i-1,j,word[1:])|| dfs(board,mark,i,j-1,word[1:])}
func getMark(board [][]byte)[][]int{ mark:=make([][]int,len(board)) for k:=0;k mark[k]=make([]int,len(board[0])) } return mark}
func cloneMark(mark [][]int)[][]int{ mark1:=make([][]int,len(mark)) for i:=0;i mark1[i]=make([]int,len(mark[0])) for j:=0;j mark1[i][j]=mark[i][j] } } return mark1}
关于“golang刷leetcode 技巧之如何解决矩阵中的路径问题”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
网站题目：golang刷leetcode技巧之如何解决矩阵中的路径问题
文章出自：
http://www.cdkjz.cn/article/pihijo.html
