题解
mlvx
·
·
题解
题意
一个 n\times m 的矩阵里，有 k 个位置有鱼。
可以放置若干个炸弹，每个炸弹可以炸到上下左右和本格五个格子，一个格子被炸后，鱼的数量会减一。
问最小需要多少个炸弹才能把全部鱼都炸掉。
分析
$a_i\le3$，显然可以对每个有鱼的格子内鱼的数量进行一个状压，一个四进制数 $s$，第 $x$ 位表示第 $x$ 个有鱼的格子的鱼的数量，$dp_s$ 表示从初始状态到状态 $s$ 所需要的炸弹的最少数量。
转移方程为 $dp_t=\min\{dp_s\}+1$，其中 $t$ 表示在 $s$ 状态上放一个炸弹，可以达到的状态。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int dx[5]={0,0,0,1,-1},dy[5]={1,-1,0,0,0};
int n,m,k,s,x[11],y[11],c[11],vis[11],dp[1<<20],fish[1010][1010];
vector<pair<int,int>>v;
int main(){
memset(dp,0x3f,sizeof dp),cin>>n>>m>>k;
for(int i=1;i<=k;i++){
cin>>x[i]>>y[i]>>c[i],(s<<=2)|=c[i],fish[x[i]][y[i]]=i;
for(int t=0;t<5;t++)
if(x[i]+dx[t]>0&&y[i]+dy[t]>0&&x[i]+dx[t]<=n&&y[i]+dy[t]<=m)
v.push_back({x[i]+dx[t],y[i]+dy[t]});
}dp[s]=0,sort(v.begin(),v.end()),unique(v.begin(),v.end());
for(int i=s;i;i--){
memset(vis,0,sizeof vis);
for(int j=k,tmp=i;j;j--){
if(tmp&3)vis[j]=1;
if((tmp&3)>c[j])goto A;
tmp>>=2;
}for(auto[x,y]:v){
int ii=i;
for(int t=0;t<5;t++){
int tmp=fish[x+dx[t]][y+dy[t]];
if(vis[tmp])ii-=(1<<(k-tmp<<1));
}dp[ii]=min(dp[ii],dp[i]+1);
}A:;
}return cout<<dp[0],0;
}
```