救救孩子吧,从俭入奢易,从奢入俭难!
func hasPath(matrix [][]byte, str string) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 || len(str) == 0 {
return false
}
m, n := len(matrix), len(matrix[0])
strsp := []byte(str)
state := make([][]int, m)
for i := range state {state[i] = make([]int, n)}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if dfs(matrix, state, i, j, strsp, 0) {
return true
}
}
}
return false
}
func dfs(matrix [][]byte, state [][]int, i int, j int, strsp []byte, pos int) bool {
m, n := len(state), len(state[0])
if 0 <= i && i < m && 0 <= j && j < n && state[i][j] == 0 {
ret := false
state[i][j] = 1
if matrix[i][j] == strsp[pos] {
if pos == len(strsp) - 1 {
return true
}
ret = dfs(matrix, state, i, j+1, strsp, pos+1) ||
dfs(matrix, state, i, j-1, strsp, pos+1) ||
dfs(matrix, state, i+1, j, strsp, pos+1) ||
dfs(matrix, state, i-1, j, strsp, pos+1)
}
if ret == false { state[i][j] = 0 }
return ret
}
return false
}