此题在数据大些，而且全是A的情况下会超时（因为要匹配到很后面才false）。通过利用数组本身作为visited标示，而且使用string引用，得意通过。
|
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
|
bool
find(vector<vector<char> > &grid, string &pattern, int
i, int
j, int
k) {
if
(k == pattern.length()) return
true;
int
m = grid.size();
int
n = grid[0].size();
if
(i < 0 || i >= m || j < 0 || j >= n) return
false;
if
(pattern[k] == grid[i][j] && grid[i][j] != ‘#‘) {
char
c = grid[i][j];
grid[i][j] = ‘#‘;
if
(find(grid, pattern, i-1, j, k+1) ||
find(grid, pattern, i+1, j, k+1) ||
find(grid, pattern, i, j-1, k+1) ||
find(grid, pattern, i, j+1, k+1)) {
grid[i][j] = c;
return
true;
} else
{
grid[i][j] = c;
return
false;
}
} else
{
return
false;
}
}bool
exists(vector<vector<char> > &grid, string pattern) {
int
m = grid.size();
if
(m == 0) return
false;
int
n = grid[0].size();
if
(n == 0) return
false;
for
(int
i = 0; i < m; i++) {
for
(int
j = 0; j < n; j++) {
if
(find(grid, pattern, i, j, 0)) return
true;
}
}
return
false;
} |