牛客網 contest4784 A膜法記錄（dfs，狀态壓縮）

題目連結：https://ac.nowcoder.com/acm/contest/4784/A

方案：

1. 注意到行數較少，可以周遊所有行是否執行攻擊的情況，然後每種情況判斷是否列攻擊次數大于剩下的含敵人的列數。

2. 時間複雜度

（題面的第二種情況資料應該沒開大最大，否則就時間就爆了）。

3. 周遊的時候可以用dfs遞歸，也可用循環，循環的時候因為本質可以看做是枚舉n位01串，是以可以用二進制進行狀态壓縮。

解法一：dfs

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int n,m,a,b,flag;
char Map[30][N];
int vis[30];

bool check()
{
    set<int> s;
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        for(int j=0;j<m;j++)
            if(Map[i][j]=='*')
                s.insert(j);
    }
    if(b>=s.size()) return true;
    else return false;
}

void dfs(int u, int k)
{
    if(u>n || k>a) //葉子結點處手動模拟一遍确定邊界。
        return;

    if(check()){ // check單獨拎出來邏輯結構會更加清晰。
        flag=1;
        return;
    }

    vis[u]=1; //vis[u]=1和vis[u]=0位置不能換，否則在中間結點處會導緻vis數組1的個數與目前棧幀的k的數值不一緻，對于全局通路數組，這一點要小心。
    dfs(u+1, k+1);
    vis[u]=0;
    dfs(u+1, k);
}

int main()
{
    int T; cin>>T;
    while(T--){
        flag=0;
        memset(vis, 0, sizeof(vis));
        cin>>n>>m>>a>>b;
        for(int i=0;i<n;i++) cin>>Map[i];
        dfs(0,0);
        if(flag) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}
           

解法二：狀壓循環

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int n,m,a,b,flag;
char Map[30][N];

int main()
{
    int T; cin>>T;
    while(T--){
        flag=0;
        cin>>n>>m>>a>>b;
        for(int i=0;i<n;i++) cin>>Map[i];

        for(int i=0;i<(1<<n);i++){
            int rcnt=0;
            for(int k=0;k<n;k++) if((i>>k)&1) rcnt++;

            if(rcnt!=a) continue; //若rcnt<a時能清除完畢，則rcnt==a時肯定也能，故隻判斷這一種情況即可

            int lcnt=0;
            for(int j=0;j<m;j++){
                for(int k=0;k<n;k++){
                    if(!((i>>k)&1) && Map[k][j]=='*') {lcnt++; break;}
                }
            }
            if(b>=lcnt){
                flag=1;
                break;
            }
        }
        if(flag) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}