殺怪物（暴力）

題目描述

為了慶祝自己的生日，小張推出一款遊戲。遊戲在一個20*20的方格上進行，上面有一些怪物，用#表示，其他是空格，用 . 表示。怪物有兩點體力。體力為0時死亡。

你可以進行以下操作：

（1）使一個橫行上的怪物體力減一

（2）使一個豎行上的怪物體力減一

對每個橫行或豎行隻能操作一次，限定n次，問最多能殺死多少個怪物。

輸入

第一行為整數n（1≦n≦40），表示操作的次數。

接下來是一個20*20的方格，#表示怪物，.表示空格。

格式參考輸入樣例。

輸出

輸出最多能殺死的怪物數量。

樣例輸入

【樣例1】

3

…

…

…###…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

【樣例2】

10

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

####################

樣例輸出

【樣例1】

2

【樣例2】

25

思路

暴力求解即可

代碼實作

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=55;
const int M=20;
const int INF=0x3f3f3f;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef pair<int,int>P;
 
int n,ans;
char mp[N][N];
int h[N],vis[N];
 
void dfs(int p,int cnt)
{
    if(cnt>=n) return ;
    int op=n-cnt,ret=0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=M;i++) vis[h[i]]++;
    for(int j=M;j && op;j--)
    {
        if(vis[j]<=op)
        {
            ret+=vis[j]*j;
            op-=vis[j];
        }
        else
        {
            ret+=op*j;
            op=0;
        }
    }
    ans=max(ans,ret);
    for(int i=p;i<=M;i++)
    {
        for(int j=1;j<=M;j++) if(mp[i][j]=='#') h[j]++;
        dfs(i+1,cnt+1);
        for(int j=1;j<=M;j++) if(mp[i][j]=='#') h[j]--;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=M;i++) scanf("%s",mp[i]+1);
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}