gym101915e

快来打我* 2022-04-24 11:16 113阅读 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进行合法检查 搜索题关键是剪枝

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关 gym224647B

gym224647B 题意： > 在二维平面中·选出一个面积最小的三角形，输出这个三角形面积的两倍。解法： > 首先，最优解一定在相邻最近的三个点...

青旅半醒/ 2024年04月20日 10:31/ 0 赞/ 77 阅读

相关 Gym - 100199C

Gym - 100199C 题意： > 其实这么长的英文题面就是想告诉我们这个题是丢手绢。解法： > 找到与 $ N $ 互质的最大整数 $ K ...

╰+哭是因爲堅強的太久メ/ 2024年04月20日 10:29/ 0 赞/ 76 阅读

相关 E - Exponial Gym - 101550E——(欧拉降幂)

b = ① ab ，b< p ②ab%∮( p )+∮( p ), b >= p [题目链接][Link 1] 本题利用知识点：...

不念不忘少年蓝@/ 2024年04月18日 08:06/ 0 赞/ 75 阅读

相关 gym第一个程序

gym安装完成之后，在pycharm中尝试运行以下代码 import gym import time env = gym.make('CartPole

电玩女神/ 2023年01月11日 09:07/ 0 赞/ 98 阅读

相关 GYM 100685 K

乱搞题统计每一个不是magic word的单词，然后每个make\_pair 然后按照公式计算答案。因为这里是乱序的统计make\_pair的情况，所以如果相邻

比眉伴天荒/ 2022年08月04日 14:41/ 0 赞/ 127 阅读

相关 Gym - 101086A （待续）

我的AC代码：G++ 405ms include<algorithm> //AC include<cstdio> usin

桃扇骨/ 2022年06月10日 11:37/ 0 赞/ 184 阅读

相关【思维】Cupcakes Gym - 101243E

Think: 1知识点：思维 2题意：n个学生去吃纸杯蛋糕，每次可以吃\[1, ai\]个，循环队列，一直到将蛋糕吃光，有一个懒惰的家伙，每次吃ai个，如果不足ai个则

分手后的思念是犯贱/ 2022年06月09日 02:13/ 0 赞/ 122 阅读

相关 Gym - 101201H

![70][] 题意：有k个区间，用他们填满1~n，不允许重叠，问留下的空隙最少是多少思路：可以从两方面考虑，第一个是正面考虑，转移方程dp\[i\]=min(dp\[j

野性酷女/ 2022年05月14日 12:51/ 0 赞/ 109 阅读

相关 Gym - 101889E 记忆化搜索

思维还是太将江华，开始一直想dp，就是这一位余数固定时取最小的一个字符串，但是字符串太大，赋值的时候超时，其实根本没必要存字符串，只要记忆化搜索，看看\[pos\]\[res\

青旅半醒/ 2022年05月09日 06:50/ 0 赞/ 140 阅读

相关 gym101915e

include <bits/stdc++.h> define N 10 using namespace std; int a

快来打我*/ 2022年04月24日 11:16/ 0 赞/ 114 阅读