自动搬运

查看原文

来自洛谷，原作者为

	mlvx 喵

搬运于2025-08-24 23:01:59，当前版本为作者最后更新于2024-10-17 15:48:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

一个 $n\times m$ 的矩阵里，有 $k$ 个位置有鱼。

可以放置若干个炸弹，每个炸弹可以炸到上下左右和本格五个格子，一个格子被炸后，鱼的数量会减一。

问最小需要多少个炸弹才能把全部鱼都炸掉。

分析

$k\le10$，显然只有最多 $5k$ 个位置放炸弹可以炸到鱼。

$a_i\le3$，显然可以对每个有鱼的格子内鱼的数量进行一个状压，一个四进制数 $s$，第 $x$ 位表示第 $x$ 个有鱼的格子的鱼的数量，$dp_s$ 表示从初始状态到状态 $s$ 所需要的炸弹的最少数量。

转移方程为 $dp_t=\min\{dp_s\}+1$，其中 $t$ 表示在 $s$ 状态上放一个炸弹，可以达到的状态。

代码

#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;
}