思路:
1.遍历起点,给每个起点对应的visit数组
2.进入check函数进行bfs
3.若word长度没了,直接true(优先级最高)
4.越界处理false
5.不匹配false
5.进入bfs,先设置visit为真,然后立个flag记录上下左右的bool,最后把visit还回来,返回flag即可
代码:
func exist(board [][]byte, word string) bool {
m := len(board)
n := len(board[0])
var visit [][]bool
//遍历起点
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
visit = make([][]bool, m)
for k := 0; k < m; k++ {
visit[k] = make([]bool, n)
}
if checkbfs(board, word, visit, i, j) {
return true
}
}
}
return false
}
func checkbfs(board [][]byte, word string, visit [][]bool, r int, c int) bool {
//正确退出(优先级第一!)
if len(word) == 0 {
return true
}
//边界处理
m := len(board)
n := len(board[0])
if r >= m || r < 0 {
return false
}
if c >= n || c < 0 {
return false
}
//不匹配
if word[0] != board[r][c] || visit[r][c] == true {
return false
}
//进行bfs
//fmt.Printf("r=%v, c=%v, now=%c\n", r, c, word[0])
visit[r][c] = true
flag := checkbfs(board, word[1:], visit, r + 1, c) ||
checkbfs(board, word[1:], visit, r - 1, c) ||
checkbfs(board, word[1:], visit, r, c + 1) ||
checkbfs(board, word[1:], visit, r, c - 1)
visit[r][c] = false
return flag
}
总结:
我居然自己写了出来
1.遍历起点+分配visit
2.正确退出条件
3.错误退出条件
4.锁定visit,四周bfs,解锁visit
5.返回flag