算法笔记：深度优先搜索（自用）

DFS是一种枚举所有完整路径以遍历所有情况的搜索方法。
常见DFS问题的描述：
枚举从N个整数中选择K个数的所有方案。

相关题目

• PAT甲级1103. Integer Factorization (30)

// given N,K,P make N = n1^p + n2^p + ... + nk^p
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

void DFS(int index, int curK,int curN, int maxSum);//index数组下标，curK现在有几个数相加，curN现在带系数的和，maxSum不带系数的和
vector<int> arrayN;//从1,2^p,3^p,....n^p选k个数使和为N  arrayN global val
int N, K, P;//global val
int maxSum_nop = -1;
vector<int> tmp, out;//tmp暂时，out为要输出的 答案

int main()
{
    cin >> N >> K >> P;
    //scanf_s("%d %d %d", &N, &K, &P);
    int num = 0;
    while(pow(num,P)<=N) {
        arrayN.push_back(num);
        num++;
    }
    int index = arrayN.size()-1,curK=0,curN=0,maxSum=0;
    DFS(index,curK,curN,maxSum);
    if (out.size() == 0) {
        cout << "Impossible" << endl;
    }
    else {
        cout << N <<" = ";
        for (int i = 0; i < out.size() - 1; i++) {
            cout << out[i] << "^"<< P <<" + ";
        }
        cout << out[out.size() - 1] << "^"<<P<<endl;
        
    }
    return 0;
}
void DFS(int index, int curK, int curN, int maxSum) {
    if (curK == K && curN == N) {//当满足结束条件的时候return
        if (maxSum > maxSum_nop) {
            maxSum_nop = maxSum;
            out = tmp;
        }
        return;
    }
    if ( curN > N || curK > K) {
        return;
    }
    if (index >= 1) {
        tmp.push_back(arrayN[index]);
        DFS(index, curK + 1, curN + pow(arrayN[index], P), maxSum + arrayN[index]);
        tmp.pop_back();
        DFS(index - 1, curK, curN, maxSum);
    }

} 

#include<iostream>
//#include<stack>
#include<vector>
using namespace std;

vector<vector<int>  > matrix = { { 0,1,1,1,0,0,1 },{ 0,0,1,0,0,0,0 },{ 0,0,0,0,1,0,0 },{ 0,0,0,1,1,1,0 },{ 1,1,1,0,1,0,0 },{ 1,1,1,1,0,0,0 } };
int m = matrix.size();
int n = matrix[0].size();
void dfs(int x, int y) {
    if (x < 0 || y<0 || x>=m || y>=n) {
        return;
    }
    if (matrix[x][y] == 0) {
        return;
    }
    matrix[x][y] = 0;
    dfs(x + 1, y);
    dfs(x, y + 1);
    dfs(x - 1, y);
    dfs(x, y - 1);
}
int main() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                count++;
                dfs(i, j);
            }
        }
    }
    cout << count << endl;
    return 0;
}