【DFS深入理解】【BFS】

【DFS深入理解】【BFS】 DFS深入理解

DFS三步骤：

1. 画出搜索树 /寻找搜索顺序
2. 收菜
3. 模拟分支过程

三个步骤吃透基本上DFS问题都可以解决

DFS+回溯+剪枝（优化） 基本上是一大类题目的模板

77.组合

class Solution {
public:
    vector> ans;
    vector temp;
    int st[21];
    void dfs(int n,int cur,int k){
        
   
        if(cur >n)  {
           if(temp.size() == k) ans.emplace_back(temp);
           return;//回溯

        } //1.收菜


        if(!st[cur]){
        st[cur] =1 ;//选
        temp.push_back(cur);
        dfs(n,cur+1,k);
        st[cur]=0;
        temp.pop_back();

        st[cur] = 2; //不选
        dfs(n,cur+1,k);
        st[cur] = 0;
        }

    }



    vector> combine(int n, int k) {
        dfs(n,1,k);
        return ans;

    }
};

46.全排列

class Solution {
public:
    vector> ans;
    vector temp;
    int st[21];
    void dfs(int n,int cur,vector& nums){
        if(cur == n )  {
            ans.emplace_back(temp);
            return;//回溯

        } //1.收菜
        
        for(int i=0;i> permute(vector& nums) {
        int n=nums.size();
        dfs(n,0,nums);
        return ans;

    }
};

784.字母大小全排列

class Solution {
public:
    vector ans;
    string temp;
    int st[100];
    void dfs(int n,int cur,string s){
        if(cur > n-1){
            ans.push_back(temp);
            return;
        } //1.收菜
        if(isdigit(s[cur])){
            temp.push_back(s[cur]);
            dfs(n,cur+1,s);
            temp.pop_back();
        }


        if(isalpha(s[cur])){
            if(isupper(s[cur])){
                st[s[cur]-'A']=1;   //改变
                temp +=(s[cur]+32);
                dfs(n,cur+1,s);
                st[s[cur]-'A']=0;
                temp.pop_back();


                st[s[cur]-'A']=0;  //不改变
                temp +=s[cur];
                dfs(n,cur+1,s);
                st[s[cur]-'A']=0;
                temp.pop_back();

            }

            else{
                st[s[cur]-'A']=1;   //改变
                temp +=(s[cur]-32);
                dfs(n,cur+1,s);
                st[s[cur]-'A']=0;
                temp.pop_back();


                st[s[cur]-'A']=0;  //不改变
                temp +=s[cur];
                dfs(n,cur+1,s);
                st[s[cur]-'A']=0;
                temp.pop_back();

            }
        }

    }




    vector letterCasePermutation(string s) {
        dfs(s.size(),0,s);
        return ans;

    }
};

BFS：

BFS基本模板：

queue q;
st[1]=1;
q.push(1);
while(q.size()){
    int t=q.front();
    q.pop();
    for(int i=h[t];~i;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            q.push[j];
            st[j]=1;
        }
    }
}
//得到队头首元素，根据首元素进行层次遍历，把未遍历过的加入队列，并d出队头元素

超级源点技巧：将所有0全部入队，且所有零能够遍历的点全部标记为st[1]。
542.01矩阵

class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    vector> updateMatrix(vector>& matrix) {
    queue> q;
    int m = matrix.size(), n = matrix[0].size();
    vector> dist(m, vector(n));
    vector> seen(m, vector(n));

    for(int i=0;i=0 && di=0 && dj 
更新超级源点技巧：利用双队列，一次队空相当于一次超级源点搜索成功，再用另外一个队列去BFS，互相递推，直到双队列均为空
 腐烂的橘子
 
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int orangesRotting(vector>& matrix) {
    queue> q;int wehave =0;
    queue> q2;
    int m = matrix.size(), n = matrix[0].size();
    vector> seen(m, vector(n));
    int min1 = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 2)
                {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
                if (matrix[i][j] == 0) {
                    seen[i][j] = 1;
                }
                if (matrix[i][j] == 1) {
                    wehave++;
                }
            }
        }  //起点全部加入队列组成超级源点

        if (wehave == 0) return 0;
        int temp=0;
        while (q.size() || q2.size()) {

            if (q.size()) {
                while (q.size()) {
                    auto l = q.front();
                    q.pop();
                    int i = l.first;
                    int j = l.second;
                    for (int d = 0; d < 4; ++d) {
                        int di = i + dirs[d][0];
                        int dj = j + dirs[d][1];
                        if (di >= 0 && di < m && dj >= 0 && dj < n && !seen[di][dj]) {
                            seen[di][dj] = 1;
                            q2.emplace(di, dj);
                            temp++;
                        }
                    }
                }  //超级源点BFS遍历
                if (temp == wehave)  return ++min1;

                else min1++;//循环完相当于一次BFS完
            }
            if (q2.size()) {
                while (q2.size()) {

                    auto t = q2.front();
                    int i = t.first;
                    int j = t.second;
                    q2.pop();
                    for (int d = 0; d < 4; ++d) {
                        int di = i + dirs[d][0];
                        int dj = j + dirs[d][1];
                        if (di >= 0 && di < m && dj >= 0 && dj < n && !seen[di][dj]) {
                            seen[di][dj] = 1;
                            q.emplace(di, dj);
                            temp++;
                        }
                    }
                }  //超级源点BFS遍历
                if (temp == wehave)  return ++min1;

                else min1++;
            }

        }
        if (temp == wehave)  return min1;
        else return -1;
    }
};

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702462.html