AcWing 23. 矩阵中的路径
原题链接
中等
作者:
蜀道难
,
2021-05-21 17:49:00
,
所有人可见
,
阅读 307
// Go语言版本
func hasPath(board [][]byte, word string) bool {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
if dfs(board, word, 0, i, j) {
return true
}
}
}
return false
}
func dfs(board [][]byte, word string, u, x, y int) bool {
// 先判断board 再判断长度
if board[x][y] != word[u] {
return false
}
// 因为u是从0开始的 所以最大增长到len(word)-1
if u == len(word)-1 {
return true
}
// 只能上下左右 所以坐标要这么写
dx := [4]int{-1, 0, 1, 0}
dy := [4]int{0, 1, 0, -1}
t := board[x][y]
board[x][y] = '*'
for i := 0; i <4; i++ {
a := x + dx[i]
b := y + dy[i]
if a >= 0 && a <len(board) && b >= 0 && b <len(board[a]) {
if dfs(board, word, u+1, a, b) {
return true
}
}
}
// 清理现场
board[x][y] = t
return false
}