1.核心思想

dfs+简单的回溯

2.问题特征

(1) 在二维棋盘或者矩阵上搜索符合某种要求的状态

3. 分析流程

dfs中最重要的是搜索顺序，做到不重不漏！！！

至于本题
step1: 依次枚举每个起点
step2: 然后上下左右四个方向上搜索，找到与字符串下一个待匹配字符相同的方向。由于不能回头重复匹配，可以通过vst数组避免重复，每次匹配下一个待匹配字符且没有访问过的继续搜索。除了单独开辟vst数组空间记录是否访问过，还可以在棋盘或者矩阵上把已经访问过的字符设置为一个特殊字符，比如 #, 因为特殊字符不会和待匹配字符串中任何一个字符匹配，也就不可能重复匹配搜索了，回溯时候再恢复。

时间复杂度：枚举单词起点 O(mn), 每一步的可能性3个方向，搜索深度是k，每个起点的时间复杂度 O(3^k), 总的时间复杂度 O(mn*3^k)

题目描述举例

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

样例

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

C 代码

int m = 0;
int n = 0;

bool dfs(char** board, int a, int b, int u, char* word, int L)
{
    //printf("a=%d, b=%d, word[%d]=%c\n", a, b, u, word[u]);
    if(board[a][b] != word[u]){
        return false;
    }
    if(u == L - 1){
        return true;
    }

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    board[a][b] = '#';
    for(int i = 0; i < 4; i++){
        int x = a + dx[i];
        int y = b + dy[i];
        if(x < 0 || x >= m || y < 0 || y >= n){
            continue;
        }

        if(board[x][y] != word[u+1]){
            continue;
        }

        if(dfs(board, x, y, u + 1, word, L)){
            return true;
        }

    }

    board[a][b] = word[u];
    return false;
}

bool exist(char** board, int boardSize, int* boardColSize, char * word){
    if(board == NULL || boardSize <= 0 || *boardColSize <= 0 || word == NULL){
        return false;
    }
    if(strlen(word) == 0){
        return true;
    }

    m = boardSize;
    n = *boardColSize;
    int len = strlen(word);
    for(int i = 0; i < boardSize; i++){
        for(int j = 0; j < *boardColSize; j++){
            if(dfs(board, i, j, 0, word, len)){
                return true;
            }
        }
    }

    return false;
}