gym101915e

快来打我* 2022-04-24 11:16 102阅读 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;
        }
    }

一道搜索题 我的做法是枚举到i行j列 先用map按照遍历顺序记录每个坐标编号 去判断i-1行 j-2列是否合法 也就是编号为x-m-2(思考为什么这样) 因为此时它周围的8个点已经确定 通过这种方法剪枝 到最后一行时 再对x-1进行合法检查 搜索题关键是剪枝