题解 | #童谣寻找问题#

考察的知识点：二维数组、回溯；

解答方法分析：

1. 判断输入的网格是否为空，如果为空则返回false。
2. 创建一个与网格相同大小的visited矩阵，用来记录每个位置的字母是否已经被访问过。
3. 遍历网格的每个位置的字母，当某个字母与目标儿童谣的首字母相同时，调用回溯函数来判断从当前位置是否存在目标儿童谣。
4. 在回溯函数中，首先判断边界条件，如果当前位置超出网格范围或者当前位置已经访问过，或者当前位置的字母与目标儿童谣的当前字母不匹配，则返回false。
5. 如果目标儿童谣的当前索引等于目标儿童的长度，说明已经找到了完整的目标儿童谣，返回true。
6. 在回溯函数中，将当前位置的母标记为已访问，然后递归调用回溯函数，分别尝试上、下、左、右四个方向的相邻位置。
7. 如果四个方向的递归用中有一个返回true，说明找到了目标儿童谣，否则，将当前位置的字母标记为未访问，并返回false。
8. 在主函数中，遍历网格的每个字母，并调用回溯函数来判断是否存在目标儿童谣。如果找到，返回true，否则返回false。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) {
            return false;
        }
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

  private:
    bool backtrack(vector<vector<char>>& board, string& word, int i, int j,
                   int index,
                   vector<vector<bool>>& visited) {
        if (index == word.size()) {
            return true;
        }
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
                visited[i][j] || board[i][j] != word[index]) {
            return false;
        }
        visited[i][j] = true;
        if (backtrack(board, word, - 1, j, index + 1, visited)
                || backtrack(board, word, i + 1, j, index + 1, visited)
                || backtrack(board, word, i, j - 1, index + 1, visited)
                || backtrack(board, word, i, j + 1, index + 1, visited)) {
            return true;
        }
        visited[i][j] = false;
        return false;
    }
};