搜索路径

1,搜索所有满足条件的路径：用栈来存储当前路径，打印满足满足条件的路径，最后栈为空

void DFS(root)
{
    if(root){
        path.push(root); //该节点入栈

        if(是一条路径)
        {
            if(该路径满足条件)
                打印该路径；
            path.pop(); //返回前要出栈
            return；  //该分支搜索结束
        }

        for(i=分支下界；i<分支上界；i++){
            DFS(分支i)；
        }

        path.push();//root的所有分支执行完，root出栈，最后栈空
    }
}

2,搜索满足条件的一条路径，并存在栈里：加一个found表明每个分支是否得到一条合适路径，得到一个时就return，不再执行后面的分支

bool DFS(root)
{
    if(root){
        path.push(root);

        if(是一条路径)
        {
            if(该路径满足条件)
                return true;
            else{
                path.pop();
                return false;
            }
        }

        bool found=false;

        for(i=分支下界；i<分支上界 && !found;i++){ //只要找到一条，就不再进行别的分支
            found=DFS(分支i)；  
        }  

        if(!found)
            path.pop();  //不是答案时要出栈，是答案时要留栈
        return found; 
    }
    return false;
}

题目要求保存符合某种条件的路径。在主函数中设置stack和DFS的初始值，然后调用DFS，初始值传给DFS函数，stack则采用值传递。
例1：二叉树中和为某值的所有路径

  vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > ans;
        vector<int> path;
        int sum=0;
        if(root)
            DFS(root,expectNumber,ans,path,sum);
        return ans;
    }

    void DFS(TreeNode* root,int t,vector<vector<int> > &ans,vector<int> &path,int &sum){
        if(root){
            path.push_back(root->val);
            sum+=root->val;

            if(!root->left && !root->right){ //是一条路径
                if(sum==t)
                    ans.push_back(path);
                path.pop_back(); //返回前要出栈
                sum-=root->val;
                return;
            }

            if(root->left)
                DFS(root->left,t,ans,path,sum);
            if(root->right)
                DFS(root->right,t,ans,path,sum);

            path.pop_back();  //返回前要出栈
            sum-=root->val;         
        }
    }

例2：机器人的运动范围
m*n的方格。机器[0,0]开始移动，每次能向左，右，上，下四个方向移动，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

class Solution {
public:
    int step[4][2]={-1,0,1,0,0,-1,0,1}; //四个方向
    int movingCount(int threshold, int rows, int cols)
    {
        if(!rows || !cols) return 0;

        const int nums=rows*cols;
        vector<int> index(nums,0); //访问标记

        DFS(threshold,rows,cols,0,0,index);

        int ans=0;
        for(int i=0;i<index.size();i++)
            ans+=index[i];

        return ans;
    }

    void DFS(int threshold, int rows, int cols,int i,int j,vector<int>& index){
        if(i<0 || i>=rows || j<0 || j>=cols) //1.不在矩阵内
            return;
        if(index[i*cols+j]==1) //2.已访问过
            return;
        if(!islegal(i,j,threshold)) //3.位置不合法
            return;

        index[i*cols+j]=1; //上述三个条件都不满足，就可以访问该位置
        for(int k=0;k<4;k++)
            DFS(threshold,rows,cols,i+step[k][0],j+step[k][1],index); //递归访问该位置周围的四个位置   
        
        return;  
    }

    bool islegal(int i,int j,int threshold){
        int sum=0;
        while(i){
            sum+=i%10;
            i/=10;
        }
        while(j){
            sum+=j%10;
            j/=10;
        }
        if(sum<=threshold)
            return true;
        return false;
    }
};