package Backtrack
func exist(board [][]byte, word string) bool {
n, m := len(board), len(board[0])
visited := make([][]bool, n)
for i := 0; i < n; i++ {
visited[i] = make([]bool, m)
}
move := [5]int{-1, 0, 1, 0, -1}
var f func(int, int, int) bool
f = func(curX, curY, index int) bool {
if index == len(word) {
return true
}
if curX < 0 || curX >= n || curY < 0 || curY >= m || visited[curX][curY] || board[curX][curY] != word[index] {
return false
}
visited[curX][curY] = true
for i := 0; i < 4; i++ {
if f(curX+move[i], curY+move[i+1], index+1) {
visited[curX][curY] = false
return true
}
}
visited[curX][curY] = false
return false
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if f(i, j, 0) {
return true
}
}
}
return false
}