回溯算法步骤:

主函数:

遍历矩阵 在每一个点调用dfs() 如果dfs返回true就返回true

dfs:

  1. 边界判断,判断输入的坐标是否在矩阵范围内,判断字符串是否被遍历完,是就返回true
  2. 存下当前坐标值
  3. 更改当前坐标对应值
  4. 4个方向上递归调用dfs
  5. 恢复当前坐标到原值
  6. 返回递归调用结果

代码:

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)
	}
}