# 单词搜索
给定一个 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 更大的情况下可以更快解决问题？
以下程序实现了这一功能，请你填补空白处内容：
```cpp
#include
#include
#include
#include
static bool dfs(char *word, char **board, bool *used,
int row, int col, int row_size, int col_size)
{
if (board[row][col] != *word)
{
return false;
}
used[row * col_size + col] = true;
if (*(word + 1) == '\0')
{
return true;
}
bool result = false;
if (row > 0 && !used[(row - 1) * col_size + col])
{
result = dfs(word + 1, board, used, row - 1, col, row_size, col_size);
}
if (!result && row < row_size - 1 && !used[(row + 1) * col_size + col])
{
result = dfs(word + 1, board, used, row + 1, col, row_size, col_size);
}
if (!result && col > 0 && !used[row * col_size + col - 1])
{
result = dfs(word + 1, board, used, row, col - 1, row_size, col_size);
}
if (!result && col < col_size - 1 && !used[row * col_size + col + 1])
{
__________________________;
}
used[row * col_size + col] = false;
return result;
}
static bool exist(char **board, int boardRowSize, int boardColSize, char *word)
{
int i, j;
int len = strlen(word);
if (len > boardRowSize * boardColSize)
{
return false;
}
bool *used = malloc(boardRowSize * boardColSize);
for (i = 0; i < boardRowSize; i++)
{
for (j = 0; j < boardColSize; j++)
{
memset(used, false, boardRowSize * boardColSize);
if (dfs(word, board, used, i, j, boardRowSize, boardColSize))
{
return true;
}
}
}
return false;
}
int main(int argc, char **argv)
{
if (argc < 3)
{
fprintf(stderr, "Usage: ./test word row1 row2...\n");
exit(-1);
}
printf("%s\n", exist(argv + 2, argc - 2, strlen(argv[2]), argv[1]) ? "true" : "false");
return 0;
}
```
## template
```cpp
#include
#include
#include
#include
static bool dfs(char *word, char **board, bool *used,
int row, int col, int row_size, int col_size)
{
if (board[row][col] != *word)
{
return false;
}
used[row * col_size + col] = true;
if (*(word + 1) == '\0')
{
return true;
}
bool result = false;
if (row > 0 && !used[(row - 1) * col_size + col])
{
result = dfs(word + 1, board, used, row - 1, col, row_size, col_size);
}
if (!result && row < row_size - 1 && !used[(row + 1) * col_size + col])
{
result = dfs(word + 1, board, used, row + 1, col, row_size, col_size);
}
if (!result && col > 0 && !used[row * col_size + col - 1])
{
result = dfs(word + 1, board, used, row, col - 1, row_size, col_size);
}
if (!result && col < col_size - 1 && !used[row * col_size + col + 1])
{
result = dfs(word + 1, board, used, row, col + 1, row_size, col_size);
}
used[row * col_size + col] = false;
return result;
}
static bool exist(char **board, int boardRowSize, int boardColSize, char *word)
{
int i, j;
int len = strlen(word);
if (len > boardRowSize * boardColSize)
{
return false;
}
bool *used = malloc(boardRowSize * boardColSize);
for (i = 0; i < boardRowSize; i++)
{
for (j = 0; j < boardColSize; j++)
{
memset(used, false, boardRowSize * boardColSize);
if (dfs(word, board, used, i, j, boardRowSize, boardColSize))
{
return true;
}
}
}
return false;
}
int main(int argc, char **argv)
{
if (argc < 3)
{
fprintf(stderr, "Usage: ./test word row1 row2...\n");
exit(-1);
}
printf("%s\n", exist(argv + 2, argc - 2, strlen(argv[2]), argv[1]) ? "true" : "false");
return 0;
}
```
## 答案
```cpp
result = dfs(word + 1, board, used, row, col + 1, row_size, col_size);
```
## 选项
### A
```cpp
result = dfs(word - 1, board, used, row, col + 1, row_size, col_size);
```
### B
```cpp
result = dfs(word + 1, board, used, row, col - 1, row_size, col_size);
```
### C
```cpp
result = dfs(word - 1, board, used, row, col - 1, row_size, col_size);
```