题解 | #童谣寻找问题# DFS 搜索

知识点

DFS 搜索

思路

在board中搜索，每个位置能否和字符串的对应位置匹配，如果能找到则返回true

实现上，可以先存下本个位置的board字符，和字符串匹配使用完后置为‘#’，防止该位置被循环使用，退出本层时还原board的字符。

AC code（C++）

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 exist(vector<vector<char> >& board, string word) {
        int n = board.size(), m = board[0].size();
        
        function<bool(int, int, int)> dfs = [&](int x, int y, int u) {
            if (u == word.size()) {
                return true;
            }
            auto t = board[x][y];
            if (t != word[u]) return false;
            board[x][y] = '#';
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 and ny >= 0 and nx < n and ny < m) {
                    if (dfs(nx, ny, u + 1)) return true;
                }
            }
            board[x][y] = t;
            return false;
        };

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (dfs(i, j, 0)) return true;
            }
        }
        return false;
    }
};