1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| // @lc code=start
impl Solution {
/// ## 解题思路
/// - dfs
pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
// 深度优先搜索
fn dfs(
board: &Vec<Vec<char>>, // 棋盘
word: &Vec<char>, // 字符数组
visited: &mut Vec<Vec<bool>>, // 回溯标记
(i, r, c): (usize, usize, usize), // 遍历标记
) -> bool {
// 边界条件, 剪枝
if r >= visited.len()
|| c >= visited[0].len()
|| visited[r][c]
|| word[i] != board[r][c]
{
return false;
}
// 终止条件
if i == word.len() - 1 {
return true;
}
// 标记遍历状态
visited[r][c] = true;
// 尝试下一步搜索
if dfs(board, word, visited, (i + 1, r + 1, c))
|| dfs(board, word, visited, (i + 1, r - 1, c))
|| dfs(board, word, visited, (i + 1, r, c + 1))
|| dfs(board, word, visited, (i + 1, r, c - 1))
{
return true;
}
// 恢复遍历状态
visited[r][c] = false;
return false;
}
let word = word.chars().collect::<Vec<_>>();
let mut visited = vec![vec![false; board[0].len()]; board.len()];
for r in 0..board.len() {
for c in 0..board[0].len() {
if dfs(&board, &word, &mut visited, (0, r, c)) {
return true;
}
}
}
false
}
}
// @lc code=end
struct Solution;
|
