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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| class Solution {
bool dfs(vector<vector<bool>>& avail,vector<vector<char>>& board, string word,int index,int si,int sj)
{
if (index == word.length())return true;
char k = word[index];
bool flag[4] = { 0,0,0,0 };
if (avail[si - 1][sj] && board[si - 1][sj] == k)
{
avail[si - 1][sj] = false;
flag[0]=dfs(avail,board, word, index + 1, si - 1, sj);
if (flag[0])
return true;
avail[si - 1][sj] = true;
}
if (avail[si][sj - 1] && board[si][sj - 1] == k)
{
avail[si][sj - 1] = false;
flag[1] = dfs(avail,board, word, index + 1, si, sj - 1);
if (flag[1])
return true;
avail[si][sj - 1] = true;
}
if (avail[si + 1][sj] && board[si + 1][sj] == k)
{
avail[si + 1][sj] = false;
flag[2] = dfs(avail,board, word, index + 1, si + 1, sj);
if (flag[2])
return true;
avail[si + 1][sj] = true;
}
if (avail[si][sj + 1]&&board[si][sj + 1] == k)
{
avail[si][sj + 1] = false;
flag[3] = dfs(avail,board, word, index + 1, si, sj + 1);
if (flag[3])
return true;
avail[si][sj + 1] = true;
}
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
int row = board.size();
int col = board[0].size();
for (int i = 0; i < row; i++)
{
board[i].insert(board[i].begin(),'#');
board[i].insert(board[i].end(), '#');
}
vector<char> tmp;
for (int i = 0; i < col + 2; i++)
tmp.push_back('#');
board.insert(board.begin(), tmp);
board.insert(board.end(), tmp);
int len = word.length();
if (len < 1)return false;
char c = word[0];
vector<pair<int,int>> start;
for (int i = 1; i <= row; i++)
for(int j=1;j<=col;j++)
if (board[i][j] == c)
start.push_back(pair<int,int>(i,j));
vector<vector<bool>> avail;
for (int i = 0; i < row + 2; i++)
{
vector<bool> t;
for (int j = 0; j < col + 2; j++)
t.push_back(true);
avail.push_back(t);
}
for (int i = 0; i < start.size(); i++)
{
int index = 1;
int si = start[i].first;
int sj = start[i].second;
avail[si][sj] = false;
if (dfs(avail,board, word, 1, si, sj))return true;
avail[si][sj] = true;
}
return false;
}
};
|