一、题目
二、思路
递归参数： 当前字符在矩阵 grid 中的行索引 i 和列索引 j ，当前目标字符（匹配的）在目标字符串 word 中的索引 k 。
终止条件：
返回 false ：当前字符和目标字符不匹配，需要return false没必要继续dfs了，而这里也可以不判断位置坐标是否越界，直接写到四个dfs前也行；
返回 true ： 当前目标字符（匹配的）在目标字符串 word 中的索引 k = len(word) - 1 ，即目标字符串 word 已全部匹配；
递归过程：
标记访问过字符（方法一）：单独设置visited二维布尔数组，如果访问过当前位置的元素，则赋值为true。
标记访问过字符（方法二）： 将 grid[i][j] 修改为 ‘/’ ，代表此元素已访问过，防止之后搜索时重复访问。
搜索当前字符的下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，并记录结果至布尔变量 flag 。
回溯当前字符： 将 board[i][j] 元素还原至初始值 。
返回值： 返回布尔量 result ，代表是否搜索到目标字符串。
三、代码
class Solution { private: vector<pair<int,int>>directions{{0,1},{0,-1},{1,0},{-1,0}}; public: bool exist(vector<vector<char>>& grid, string word) { int high = grid.size(); int width = grid[0].size(); vector<vector<int>> visited(high, vector<int>(width)); //分别从每个单词开始dfs for(int i = 0; i < high; i++){ for(int j = 0; j < width; j++){ bool flag = dfs(grid, visited, i, j, word, 0); if(flag){ return true; } } } return false; } bool dfs(vector<vector<char>>&grid, vector<vector<int>>&visited, int i, int j, string& word, int k){ if(grid[i][j] != word[k]){ //当前字符不匹配 return false; } if(k == word.length() - 1){ //当前已经访问到末尾，即完成word匹配 return true; } //标记访问过 visited[i][j] = true; bool result = false; for(auto dir: directions){ int x = i + dir.first, y = j + dir.second; //若没有越界 if(isarea(grid, x, y)){ //若没有访问过 if(!visited[x][y]){ bool flag = dfs(grid, visited, x, y, word, k + 1); if(flag){ result = true; break; } } } } //恢复原状 visited[i][j] = false; return result; } bool isarea(vector<vector<char>>&grid,int x,int y){//判断点是否在网格内 if(x>=0 && x<grid.size() && 0<=y && y<grid[0].size()){ return true; }else{ return false; } } };
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)