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
60
61
62
63
64
65
66
67
68
69
70
71
| bool find(vector<vector<char>>& board, bool** access, string s, int index, int x, int y)
{
if (index == s.length())return true;
if (access[x][y + 1] && board[x - 1][y] == s[index])
{
access[x][y + 1] = false;
bool ext = find(board, access, s, index + 1, x - 1, y);
if (ext)return true;
access[x][y + 1] = true;
}
if (access[x + 2][y + 1] && board[x + 1][y] == s[index])
{
access[x + 2][y + 1] = false;
bool ext = find(board, access, s, index + 1, x + 1, y);
if (ext)return true;
access[x + 2][y + 1] = true;
}
if (access[x + 1][y] && board[x][y - 1] == s[index])
{
access[x + 1][y] = false;
bool ext = find(board, access, s, index + 1, x, y - 1);
if (ext)return true;
access[x + 1][y] = true;
}
if (access[x + 1][y + 2] && board[x][y + 1] == s[index])
{
access[x + 1][y + 2] = false;
bool ext = find(board, access, s, index + 1, x, y + 1);
if (ext)return true;
access[x + 1][y + 2] = true;
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int len = word.length(); if (!len)return true;
int m = board.size();
if (!m)return false;
int n = board[0].size();
bool** access = new bool*[m + 2];
for (int i = 0; i<m+2; i++)
access[i] = new bool[n + 2];
for (int i = 1; i<m + 1; i++)
for (int j = 1; j<n + 1; j++)
access[i][j] = true;
for (int i = 0; i<m + 2; i++)
{
access[i][0] = false;
access[i][n + 1] = false;
}
for (int i = 0; i<n + 2; i++)
{
access[0][i] = false;
access[m + 1][i] = false;
}
for (int i = 0; i<board.size(); i++)
{
for (int j = 0; j<board[0].size(); j++)
{
if (board[i][j] == word[0])
{
access[i + 1][j + 1] = false;
bool ext = find(board, access, word, 1, i, j);
if (ext)return true;
access[i + 1][j + 1] = true;
}
}
}
return false;
}
|