基于递归方式实现的DFS算法解本题

我想这道题出的目的就是这个，说是递归，其实还是结合了dfs的算法，一套路走到黑不行在递归回溯。

回到本题，本题要求求出一共有多少种售出座位的方式，即在m*n的总座位上有多少个能保证k个位置满足各个座位不上下左右相邻的情况，可知，我们要找出每一种满足条件的情况，并计数统计，那就是要从第一个位置开始，往下找符合要求的位置，然后用vector容器记录这个符合要求的位置，在从这个基础上找第三个位置，以此类推，如果这条路走完了发现没有满足k个位置的要求，就说明上一个位置虽然空，但是可能影响其他空位了，就要回溯，不记录这个位置，继续找其他位置来遍历，如果满足k的要求了，就让记录情况的变量++，然后继续走，这样就能遍历所有正确的情况，获得正确答案。

回溯这一操作可以用递归实现，我们满足条件的一直递下去，等某一次未满足条件，就归回来实现回溯，同时pop_back掉这个错误的位置，继续往下循环遍历，找另一个符合条件的位置。

此题最重要的还是对递归的熟悉运用，学会此题对递归这个方法理解会加深很多，作为算法小白，此题解用来梳理自己思路，记录成长过程，如果能帮到别人也算是自己一大荣幸。

以下为代码实现

using namespace std;
#define int long long
const int MOD=420047;
vector<pair<int,int>>seat;
bool isNull(pair<int,int>a,pair<int,int>b){//判断是不是相邻
    return (abs(a.first-b.first)==1&&a.second==b.second)
        ||(abs(a.second-b.second)==1&&a.first==b.first);
}
void digui(int start,int &res,int k,int total,vector<int> &a){
    if(a.size()==k){
        res=(res+1)%MOD;
        return;
    }
    else{
        for(int i=start;i<total;i++){
            bool flag=true;
           for(int idx:a){
               if(isNull(seat[i],seat[idx])){
                   flag=false;
                   break;
               }//判断是否相邻
           }
            if(flag){
                a.emplace_back(i);
                digui(i+1,res,k,total,a);
                a.pop_back();//回溯操作，下一次递归全走完循环不满足就回溯
            }
        }
    }
    
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int res=0;
        int m,n,k;
        cin>>m>>n>>k;
        seat.clear();//要记住每次while都要清除seat里的内容，因为seat是全局变量，也可定义在main函数里
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                seat.emplace_back(i,j);//储存位置坐标，为了调用第一个判断相邻的bool函数用
            }
        }
        int total=m*n;
        vector<int>a;//用来存空闲位置组合的动态数组
        //分情况考虑
        if(k==0) res=1;
        else if(k>0) digui(0,res,k,total,a);

        else res=0;
        cout<<res<<endl;
    }
}

以下为其他想法，与递归无关

这题其实也就是找所有排列，然后符合条件的k个排列就算一种情况，那我们是不是也可以调用next_permutation函数，来找到该数组的所有排列然后依次遍历来判断呢，这样就可以用枚举方式来解决本问题，省的用递归了