题解 | #童谣寻找问题#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */

    vector<pair<int,int>> v = {{-1,0},{1,0},{0,-1},{0,1}};
    bool ans = false;

    void dfs(vector<vector<char>>& board, int i, int j, string word, int index, vector<vector<bool>> flag, string str)
    {
        if(i<0 || i>=board.size() || j<0 || j>=board[0].size())
            return;

        if(str == word)
        {
            ans = true;
            return;
        }

        if(board[i][j]==word[index] && !flag[i][j])
        {
            flag[i][j] = true;
            str.push_back(word[index]);
            for(auto [t_i,t_j]:v)
                dfs(board, i+t_i, j+t_j, word, index+1, flag, str);
        }
    }

    bool exist(vector<vector<char> >& board, string word) {
        // write code here
        
        // 深度优先搜索
        int row = board.size();
        int col = board[0].size();
        // 避免重复遍历
        vector<vector<bool>> flag(row,vector<bool>(col,false));
        string str = "";

        for(int i=0; i<row; ++i)
        {
            for(int j=0; j<col; ++j)
            {
                if(board[i][j]==word[0])
                    dfs(board, i, j, word, 0, flag, str);
            }
        }

        return ans;
    }
};