大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察深度优先搜索（DFS）算法，需要在二维字符网格上搜索是否存在给定的儿童谣。

题目解答方法的文字分析

我们可以使用深度优先搜索（DFS）来解决这个问题。具体步骤如下：

  1. 遍历二维字符网格 board 中的每一个格子，将每个格子都作为搜索的起点，开始 DFS 搜索。
  2. 在 DFS 搜索中，首先判断当前格子是否超出网格范围或者当前格子的字母与待搜索的 word 的首字母不匹配，若是，则直接返回 false，表示当前搜索路径不满足条件。
  3. 若当前格子的字母与待搜索的 word 的首字母匹配，则进行深度优先搜索。在搜索过程中，我们需要标记当前格子已被访问，避免重复使用。
  4. 在 DFS 的过程中，逐步匹配 word 的每个字符，并在水平或垂直相邻的格子上进行下一步搜索。如果成功搜索到整个 word，则返回 true，否则回溯并尝试其他路径。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 判断儿童谣 word 是否存在于网格 board 中。
     * 
     * @param board char字符型vector<vector<>>，二维字符网格
     * @param word string字符串，待搜索的儿童谣
     * @return bool布尔型，如果 word 存在于网格中，返回 true，否则返回 false
     */
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    /**
     * DFS 搜索函数，在网格 board 中搜索儿童谣 word。
     * 
     * @param board char字符型vector<vector<>>，二维字符网格
     * @param i int整型，当前格子的行坐标
     * @param j int整型，当前格子的列坐标
     * @param word string字符串，待搜索的儿童谣
     * @param index int整型，当前需要匹配的 word 字符索引
     * @return bool布尔型，如果成功搜索到整个 word，返回 true，否则返回 false
     */
    bool dfs(vector<vector<char>>& board, int i, int j, const string& word, int index) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index]) {
            return false;
        }

        if (index == word.size() - 1) {
            // 已经匹配到了最后一个字符，搜索成功
            return true;
        }

        char tmp = board[i][j];
        board[i][j] = '#'; // 将当前格子标记为已访问

        // 搜索相邻的格子
        if (dfs(board, i + 1, j, word, index + 1) || dfs(board, i - 1, j, word, index + 1) ||
            dfs(board, i, j + 1, word, index + 1) || dfs(board, i, j - 1, word, index + 1)) {
            return true;
        }

        board[i][j] = tmp; // 回溯，将当前格子还原为原来的字母
        return false;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！