搜索与回溯算法_搜索专题 一本通 一本通2018-第五章-搜索与回溯算法 : 1502: 【搜索基础】有重复

 这道题目的做法是采用dfs的递归方式去做，我们要在矩阵中找到是否存在字符串，递归循环的结束条件是当我们的检索到了最后一个字符，即可返回true，那么这个，假如下标越界或者此位置的字符与我们要找的字符不同，同样也是返回false，当然假如相同然后此时字符串也没有搜索完，我们就把当前的字符位置设为空代表我们走过此位置，防止重复搜索，然后，递归地去 board[i][j] 的上下左右四个方向去找，剩下的路径，在 dfs 的过程当中，如果某条路已经不通了，那么那么需要回溯，也就是将 visited[i][j] 位置的布尔值重新赋值为 fasle，最后，返回 ans 即可。

 bool find(vector<vector<char>>& board,int i,int j,int count,string word)

    {

        if(count==word.size()) return true;

        if(i<0||i>board.size()-1) return false;

        if(j<0||j>board[0].size()-1) return false;

        if(board[i][j]!=word[count]) return false;

        

        board[i][j]='0';

        bool ans= find(board,i+1,j,count+1,word)||find(board,i-1,j,count+1,word)||find(board,i,j-1,count+1,word)||find(board,i,j+1,count+1,word);

        board[i][j]=word[count];

        return ans;

    }

    

    bool exist(vector<vector<char>>& board, string word) {

           if(board.size()==0||word.size()==0) return false;

           

           for(int i=0;i<board.size();++i)

           {

               for(int j=0;j<board[0].size();++j)

               {

                  if(find(board,i,j,0,word)) {return true;}

               }

           }

           return false;

        }

深度优先搜索： 可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 。

回溯返回值： 因为起点0 0，返回 1 + 向右和向下的方向，代表从本单元格递归搜索的可达解总数。因为只要进入了递归就至少有一次。

 int kit(int x)

    {

        int ans=x%10+x/10;

        return ans;

    }

    

   int dfs(int i,int j,int m,int n,int k,vector<vector<int>>&map)

   {

       if(i>=m||j>=n||i<0||j<0||map[i][j]==1||(kit(i)+kit(j)>k)) return 0;

       else

       {

           map[i][j]=1;

           return dfs(i+1,j,m,n,k,map)+dfs(i,j+1,m,n,k,map)+1;

       }

   }

    int movingCount(int m, int n, int k) {

        vector<int> w(n, 0);  

        vector< vector<int> > arr(m, w);  

        return dfs(0,0,m,n,k,arr);

    }