思路:
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