# 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int a = 3, b = 4;
vector> board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
string word = "ABCCED";
bool res;
res = sol.exist(board, word);
cout << res;
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
vector> dirs{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool exist(vector> &board, string word)
{
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (dfs(board, word, 0, i, j))
return true;
}
}
return false;
}
bool dfs(vector> &board, string &word, int idx, int x, int y)
{
if (board[x][y] != word[idx])
return false;
if (idx == word.size() - 1)
return true;
char tmp = board[x][y];
board[x][y] = 0;
for (const auto &dir : dirs)
{
if (x + dir[0] < 0 || x + dir[0] >= board.size() || y + dir[1] < 0 || y + dir[1] >= board[0].size())
continue;
if (dfs(board, word, idx, x + dir[0], y + dir[1]))
return true;
}
board[x][y] = tmp;
return false;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
bool search(vector> &board, string word, int i, int j, int pos)
{
if (pos == word.size())
return true;
if (i < 0 || j < 0 || i >= board.size() || j >= board[i].size())
return false;
if (word[pos] != board[i][j])
return false;
char temp = board[i][j];
board[i][j] = '.';
bool result = search(board, word, i + 1, j, pos + 1) || search(board, word, i - 1, j, pos + 1) || search(board, word, i, j - 1, pos + 1) || search(board, word, i, j + 1, pos + 1);
board[i][j] = temp;
return result;
}
bool exist(vector> &board, string word)
{
for (int i = 0; i < board.size(); i++)
for (int j = 0; j < board[i].size(); j++)
if (search(board, word, i, j, 0))
return true;
return false;
}
};
```
### B
```cpp
class Solution
{
public:
bool exist(vector> &board, string word)
{
rows = board.size(), columns = board[0].size();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
if (backtrack(board, word, i, j, 0))
return true;
}
}
return false;
}
private:
int rows, columns;
bool backtrack(vector> &board, string &word, int x, int y, int index)
{
if (x >= rows || x < 0 || y >= columns || y < 0 || board[x][y] != word[index])
{
return false;
}
if (index == word.size() - 1)
{
return true;
}
board[x][y] = ' ';
if (backtrack(board, word, x - 1, y, index + 1) || backtrack(board, word, x + 1, y, index + 1) || backtrack(board, word, x, y - 1, index + 1) || backtrack(board, word, x, y + 1, index + 1))
{
return true;
}
board[x][y] = word[index];
return false;
}
};
```
### C
```cpp
class Solution
{
public:
bool DFS(vector> &board, string word, int row, int col, int index, vector> &flag)
{
if (index == word.length())
{
return true;
}
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != word[index])
{
return false;
}
if (0 == flag[row][col])
{
flag[row][col] = 1;
if (DFS(board, word, row - 1, col, index + 1, flag))
{
return true;
}
if (DFS(board, word, row + 1, col, index + 1, flag))
{
return true;
}
if (DFS(board, word, row, col - 1, index + 1, flag))
{
return true;
}
if (DFS(board, word, row, col + 1, index + 1, flag))
{
return true;
}
flag[row][col] = 0;
}
return false;
}
bool exist(vector> &board, string word)
{
int m = board.size();
int n = board[0].size();
int k = word.length();
vector> flag(m, vector(n, 0));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (DFS(board, word, i, j, 0, flag))
{
return true;
}
}
}
return false;
}
};
```