problem: https://oj.leetcode.com/problems/word-search/
代码:https://play.golang.org/p/d5wP691Pbg
package main import ( "fmt" ) func main() { arr := [][]byte{ {'A','B','C','E'},{'S','F','S'},{'A','D','E',} //word := []byte("ABCESC") word := []byte("SFCE") arrI,arrJ,ok := FindFirstCharPositions(arr,word[0]) if ok { fmt.Printf("%d,%d\n",arrI,arrJ) } fmt.Println(DFSTraverse(arr,word,arrJ)) } func DFSTraverse(arr [][]byte,word []byte,arrI []int,arrJ []int) (ret bool) { //初始化visited函数 lenArr := len(arr) visited := make([][]bool,lenArr) for i := 0; i < lenArr; i++ { visited[i] = make([]bool,len(arr[i])) } lenArrI := len(arrI) //lenArrJ := len(arrJ) for i := 0; i < lenArrI; i++ { //fmt.Println(i) ret = DFS(arr,visited,arrI[i],arrJ[i]) if ret == true { return true } } return } //dfs traverse,when found return true func DFS(arr [][]byte,index int,visited [][]bool,i int,j int) (ret bool) { if i < 0 || j < 0 || i >= len(visited) || j >= len(visited[i]) || visited[i][j] { return false } if index == len(word) { return true } if arr[i][j] != word[index] { return false } fmt.Printf("%c:%d,%d ",word[index],i,j) visited[i][j] = true //标识为已访问 index++ //fmt.Println("yes") ret = DFS(arr,index,i-1,j) || DFS(arr,j+1) || DFS(arr,i+1,j-1) visited[i][j] = false return ret } func FindFirstCharPositions(arr [][]byte,c byte) (arrI []int,arrJ []int,ok bool) { lenArrRow := len(arr) if lenArrRow == 0 { return } lenArrCol := len(arr[0]) for i := 0; i < lenArrRow; i++ { for j := 0; j < lenArrCol; j++ { if arr[i][j] == c { arrI = append(arrI,i) arrJ = append(arrJ,j) ok = true } } } return }