gym101915e-蒲公英云

gym101915e

快来打我* 2022-04-24 11:16 246阅读 0赞

#include <bits/stdc++.h>
#define N 10
using namespace std;
int a[N][N];
int n,m,k,ans=0,sum=0;
map<int,pair<int,int> > mp;
int xx[8]={1,1,1,0,0,-1,-1,-1};
int yy[8]={0,1,-1,-1,1,0,1,-1};
bool judge(int cur){
    int x=mp[cur].first,y=mp[cur].second;
    int s1=0,s2=0;
    for(int i=0;i<8;i++){
        int tx=x+xx[i];
        int ty=y+yy[i];
        if(a[tx][ty]==1) s1++;
        if(a[tx][ty]==2) s2++;
    }
    if(a[x][y]==2&&s1>0||a[x][y]==1&&s2<=k){
        return true;
    }else{
        return false;
    }
}
void dfs(int cur){
    int x=mp[cur].first,y=mp[cur].second;
    if(n*m+1-cur+sum<ans) return;
    if(cur>m+2){
        if(!judge(cur-m-2)) return;
    }
    if(cur>(n-1)*m+2){
        if(!judge(cur-2)) return;
    }
    if(cur==n*m+1){
        if(!judge(cur-m-1)) return;
        if(!judge(cur-1)) return;
        ans=max(ans,sum);
        return;
    }
    a[x][y]=1;
    dfs(cur+1);
    a[x][y]=0;
    a[x][y]=2;
    sum++;
    dfs(cur+1);
    sum--;
    a[x][y]=0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int i,j,cnt=0;
        ans=0;
        sum=0;
        cin>>n>>m>>k;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                mp[++cnt]=make_pair(i,j);
            }
        }
        dfs(1);
        cout<<ans<<endl;
    }
}