P2825 [HEOI2016/TJOI2016] 游戏 与 P10945 Place the Robots

本文中的机器人同炸弹,主要是题目描述不同,两道题目做法是本质相同的。

思路:

先说一下没有墙怎么办,那么当一个位置放了机器人之后,这个机器人所在的行和列是不能继续放置的。

那么发现行和列几乎是独立的,考虑建二分图,若 \((i,j)\) 能放一个机器人,那么给 \(i \to j\) 建一条边。

那么答案就是这个二分图的最大匹配,这样每个匹配的就代表着一个机器人所放的位置。

现在再考虑有墙的情况,有墙时,机器人所放的激光无法穿透过去,则在墙另外一边依旧可能可以放置机器人。

发现墙就是把行或列分为了几个部分,每个部分互不干扰,则考虑每遇到墙,就新起一行表示当前位置到下一个墙或者这一行的末尾的放块;列同理。

直接跑匈牙利算法即可。

P2825 [HEOI2016/TJOI2016] 游戏 Code:
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2505;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
inline char get(){
    char c;
    while((c=getchar())!='*'&&c!='x'&&c!='#');
    return c;
}
ll n,m,id,ans,s1,s2;
ll a[N],f[N];
ll h[N][N];
char s[N][N];
vector<ll> E[N];
void add(ll u,ll v){
	E[u].push_back(v);
}
bool dfs(ll u){
	for(auto v:E[u]){
		if(f[v]==id)
		  continue;
		f[v]=id;
		if(!a[v]||dfs(a[v])){
			a[v]=u;
			return 1;
		}
	}
	return 0;
}
void Match(){
	for(int i=1;i<=s1;i++){
		id=i;
		if(dfs(i))
		  ans++;
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
		s[i][j]=get();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='#')
			  continue;
			if(s[i][j-1]=='#'||j==1)
			  ++s1;
			h[i][j]=s1;
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(s[i][j]=='#')
			  continue;
			if(s[i-1][j]=='#'||i==1)
			  ++s2;
			if(h[i][j]&&s[i][j]=='*')
			  add(h[i][j],s2);	
		}
	}
	Match();
	write(ans);
	return 0;
}
P10945 Place the Robots Code:
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2505;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
inline char get(){
    char c;
    while((c=getchar())!='*'&&c!='o'&&c!='#');
    return c;
}
ll T,n,m,cnt,id,ans,s1,s2;
ll a[N],f[N];
ll h[N][N];
char s[N][N];
vector<ll> E[N];
void add(ll u,ll v){
	E[u].push_back(v);
}
bool dfs(ll u){
	for(auto v:E[u]){
		if(f[v]==id)
		  continue;
		f[v]=id;
		if(!a[v]||dfs(a[v])){
			a[v]=u;
			return 1;
		}
	}
	return 0;
}
void Match(){
    memset(f,0,sizeof(f));
    memset(a,0,sizeof(a));
	for(int i=1;i<=s1;i++){
		id=i;
		if(dfs(i))
		  ans++;
	}
}
void solve(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
		s[i][j]=get();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='#')
			  continue;
			if(s[i][j-1]=='#'||j==1)
			  ++s1;
			h[i][j]=s1;
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(s[i][j]=='#')
			  continue;
			if(s[i-1][j]=='#'||i==1)
			  ++s2;
			if(h[i][j]&&s[i][j]=='o')
			  add(h[i][j],s2);	
		}
	}
	Match();
    printf("Case :%lld\n",++cnt);
	write(ans);
    putchar('\n');
    For(i,1,max(s1,s2))
      E[i].clear();
    s1=s2=ans=0;
}
int main(){
    T=read();
    while(T--)
      solve();
	return 0;
}