舞蹈链求助
查看原帖
舞蹈链求助
438957
retep楼主2022/4/26 12:00

先不管tle,这个为什么会全wa呢

#include<bits/stdc++.h>
#define N 505
#define ll long long
using namespace std;

int n,m,a[N][N];
bool vst[N];
vector<int> ans;

bool dfs(int i,int k){
    if(k==m){
        for(int j=0;j<ans.size();j++)cout<<ans[j]<<" ";
        return true;
    }
    for(int j=i;j<=n;j++)
        if(!vst[j]){
            ans.push_back(j);
            for(int x=1;x<=m;x++)
                if(a[j][x]){
                    k++;
                    for(int y=j+1;y<=n;y++)
                        if(a[y][x])vst[y]=true;
                }
            if(dfs(j+1,k))return true;
            for(int x=1;x<=m;x++)
                if(a[j][x]){
                    k--;
                    for(int y=j+1;y<=n;y++)
                        if(a[y][x])vst[y]=false;
                }
            ans.pop_back();
        }
    return false;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];
    if(!dfs(1,0))cout<<"No Solution!";
    return 0;
}
2022/4/26 12:00
加载中...