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