给定一张 n×m 的网格地图:其中 *
代表空地,炸弹的威力可以穿透,可以在空地上放置一枚炸弹。
x
代表软石头,炸弹的威力可以穿透,不能在此放置炸弹。#
代表硬石头,炸弹的威力是不能穿透的,不能在此放置炸弹。
例如:给出 1×41×4 的网格地图 *xx*
,这个地图上最多只能放置一个炸弹。给出另一个1×4 的网格地图 *x#*
,这个地图最多能放置两个炸弹。
给出一张 n×m 的网格地图,问最多能放置多少炸弹
和某棋盘游戏一样,但有障碍物。 重新定义每个位置的行和列,跑最大流
#include <iostream> #include <queue> #include <vector> #include <cstring> using namespace std; const int N =5004,M=6e5+3; const int inf =1e9+7; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T,n,m; int dis[M],now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } char a[N][N]; int cnt1,cnt2,L[N][N],C[N][N] ; signed main(){ int i,j; cin>>n>>m; for(i=1;i<=n;++i) for(j=1;j<=m;++j) cin>>a[i][j]; for(i=1;i<=n;i++) a[i][0]='#'; for(i=1;i<=m;i++) a[0][i]='#'; for(i=1;i<=n;++i) for(j=1;j<=m;++j){ if(a[i][j]=='#') continue; if(a[i][j-1]=='#') cnt1++; if(a[i][j]=='*') L[i][j]=cnt1; } for(j=1;j<=m;++j) for(i=1;i<=n;i++){ if(a[i][j]=='#') continue; if(a[i-1][j]=='#') cnt2++; if(a[i][j]=='*') C[i][j]=cnt2; } //DEBUG S=0,T=cnt1+cnt2+1; for(i=1;i<=cnt1;i++) add_(S,i,1); for(i=1;i<=cnt2;i++) add_(i+cnt1,T,1); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]=='*') add_(L[i][j],cnt1+C[i][j],1); int ans=0; while(bfs()) ans+=dfs(S,inf); cout<<ans<<endl; }