回溯算法步骤:
主函数:
遍历矩阵 在每一个点调用dfs() 如果dfs返回true就返回true
dfs:
- 边界判断,判断输入的坐标是否在矩阵范围内,判断字符串是否被遍历完,是就返回true
- 存下当前坐标值
- 更改当前坐标对应值
- 4个方向上递归调用dfs
- 恢复当前坐标到原值
- 返回递归调用结果
代码:
package main
import "fmt"
func hasPath(matrix [][]byte,word string)bool {
if len(matrix[0])==0 && len(matrix)==0 {
return false
}
for i:=0;i<len(matrix);i++{
for j:=0;j<len(matrix[0]);j++{
if dfs(matrix,word,i,j,0){
return true
}
}
}
return false
}
func dfs(matrix [][]byte,word string, i int,j int, index int)bool{
if i<0 || i>=len(matrix) || j<0 || j>=len(matrix[0]) || matrix[i][j]!=word[index]{
return false
}
if index == len(word)-1{
return true
}
tmp:=matrix[i][j]
matrix[i][j] = '.'
res:=dfs(matrix,word,i+1,j,index+1)||dfs(matrix,word,i-1,j,index+1)||dfs(matrix,word,i,j-1,index+1)||dfs(matrix,word,i,j+1,index+1)
matrix[i][j] = tmp
return res
}
func main(){
x:=[][]byte{
{'a','b','c','e'},
{'s','f','c','s'},
{'a','d','e','e'},
}
y:="abcced"
if hasPath(x,y){
fmt.Println(true)
}
}