题解 | #童谣寻找问题#

考察知识点：回溯

题目分析：

分两个阶段，第一个阶段是找递归的入口，第二个阶段是递归寻找童谣。递归入口只能通过循环遍历一遍数组来进行查找，一旦查找到递归入口，那么我们就开始进行递归，尝试查找整个童谣。

查找的起始位置当然是上一次在board上匹配到的位置。我们看这个位置的上下左右是否是我们当前要找的字符，如果是那么我们将要进行下一层递归，查找下一个字符。

注意一个格子只能查找一次，我们可以通过数组标记各个格子是否被查找过，注意在回溯时应该恢复现场。

当我们要查找的字符的索引大于等于word的长度，说明我们已经找到了整个童谣，直接返回true即可。

所用编程语言：Ｃ++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool dfs(vector<vector<char>> &board, int i, int j, string &word, int index, int st[][8]) {
        int m = board.size();
        int n = board[0].size();
        int size = word.size();
        bool success = false;
        if (index >= size) 
            return true;
        for (int x = 0; x < 4; x++) {
            int row = i + dx[x];
            int col = j + dy[x];
            if (row >= 0 && row < m && col >= 0 && col < n && (!st[row][col]) && board[row][col] == word[index]) {
                st[row][col] = true;
                success |= dfs(board, row, col, word, index + 1, st);
                st[row][col] = false;
            }
        }
        return success;
    }
    bool exist(vector<vector<char> >& board, string word) {
        // write code here
        bool success = false;
        int m = board.size();
        int n = board[0].size();
        int st[8][8] = {0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != word[0]) 
                    continue;
                else {
                    st[i][j] = true;
                    success |= dfs(board, i, j, word, 1, st);
                    st[i][j] = false;
                }
            }
        }
        return success;
    }
};