题目描述
大雨侵袭了牧场。牧场是一个 \(R \times C\) 的矩形，其中 \(1\leq R，C\leq 50\)。大雨将没有长草的土地弄得泥泞不堪，可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。 为了防止她们的蹄子被弄脏，农场主决定在泥泞的牧场里放置一些木板。每一块木板的宽度为 \(1\) 个单位，长度任意。每一个板必须放置在平行于牧场的泥地里。农场主想使用最少的木板覆盖所有的泥地。一个木板可以重叠在另一个木板上，但是不能放在草地上。
输入格式
第一行：两个整数 \(R\) 和 \(C\)。
第二行到第 \(R + 1\) 行：第 \(i + 1\) 行有 \(C\) 个字符串，表示第 \(R\) 的地形，“*”
代表泥地，“.”代表草地。
输出格式
一个整数：表示最少需要多少木板。
40pts
暴力dfs，枚举每个泥泞，看是往上、下、左、右哪个方向延伸。最坏复杂度 \(nm\times 4^{nm}\)，基本无法得分。但我们可以在此基础上进行最优性剪枝（在当前答案大于全局答案时返回）、跳过草地、特判单个泥泞、特判狭窄泥泞、特判左向 \(left-right-single\) 、右向 \(up-down-single\)和使用栈等一系列的优化来获得 \(60\) 分的好成绩。
代码：
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define db(x) cout<<endl<<x<<endl;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,m;
int a[70][70];
int ans=INF;
void draw(){
foru(i,1,n){
foru(j,1,m){
cout<<a[i][j]<<' ';
}
HH;
}
}
class Node{
public:
int x,y;
};
void dfs(int x,int y,int as){
if(as>=ans) return ;
if(x==n+1){//end
ans=min(ans,as);
return ;
}
if(a[x][y]!=1){//continue
if(y==m) dfs(x+1,1,as);
else dfs(x,y+1,as);
return ;
}
if(a[x-1][y]==0 && a[x+1][y]==0 && a[x][y+1]==0 && a[x][y-1]==0){//single_check
a[x][y]=2;
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
a[x][y]=1;
return ;
}
stack<Node> s;//recover
if(a[x-1][y]==0 && a[x+1][y]==0){//up-down-single
for(int i=y;;i--){
if(a[x][i]==0){
break;
}
if(a[x][i]==1) s.push((Node){x,i});
a[x][i]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
for(int i=y;;i++){
if(a[x][i]==0){
break;
}
if(a[x][i]==1) s.push((Node){x,i});
a[x][i]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
return ;
}
if(a[x][y-1]==0 && a[x][y+1]==0){//left-right-single
for(int i=x;;i--){
if(a[i][y]==0){
break;
}
if(a[i][y]==1) s.push((Node){i,y});
a[i][y]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
for(int i=x;;i++){
if(a[i][y]==0){
break;
}
if(a[i][y]==1) s.push((Node){i,y});
a[i][y]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
return ;
}
//last,all
//do x
for(int i=x;;i--){
if(a[i][y]==0){
break;
}
if(a[i][y]==1) s.push((Node){i,y});
a[i][y]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
for(int i=x;;i++){
if(a[i][y]==0){
break;
}
if(a[i][y]==1) s.push((Node){i,y});
a[i][y]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
//do y
for(int i=y;;i--){
if(a[x][i]==0){
break;
}
if(a[x][i]==1) s.push((Node){x,i});
a[x][i]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
for(int i=y;;i++){
if(a[x][i]==0){
break;
}
if(a[x][i]==1) s.push((Node){x,i});
a[x][i]=2;
}
if(y==m) dfs(x+1,1,as+1);
else dfs(x,y+1,as+1);
while(!s.empty()){
a[s.top().x][s.top().y]=1;
s.pop();
}
}
signed main(){
// freopen("cover.in","r",stdin);
// freopen("cover.out","w",stdout);
n=RIN,m=RIN;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<m;j++){
if(s[j]=='*'){
a[i][j+1]=1;
}
}
}
dfs(1,1,0);
cout<<ans;
return 0;
}
100pts
考虑按照套路进行建模。
我们把所有的泥地分成若干个横连通块和纵连通块，把他们分别作为二分图的左右两部分。泥泞意味着把泥泞所在的横连通块和纵联通块连边。于是我们要找到最少的木板，变成了一个最小点覆盖问题。所以直接求二分图最大匹配即可。
为什么是最小点覆盖呢？因为我们每找到一个点，就相当于选中了一个“横/纵联通块”，放置了一块木板，而在二分图里的“被控制”的边，对应到题目就代表着“这个联通块上的泥泞已经被木板覆盖”，所以可以用最小点覆盖解决。
代码：
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define db(x) cout<<endl<<x<<endl;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,m,xx,yy;
int a[70][70],b[70][70];
bool c[70][70];
int ans=0;
const int MAXM=500005;
class Edge{
public:
int v,w,nxt;
}e[MAXM<<1];
int ehead[MAXN],ecnt;
inline void add_e(int u,int v,int w=0){e[++ecnt]={v,w,ehead[u]},ehead[u]=ecnt;}
bool vis[MAXN];
int match[MAXN];
bool find(int x){
for(int i=ehead[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]) continue;
vis[v]=1;
if(match[v]==0 || find(match[v])){
match[v]=x;
return true;
}
}
return false;
}
signed main(){
n=RIN,m=RIN;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=1;j<=m;j++){
if(s[j-1]=='*'){
c[i][j]=true;
if(j>1&&c[i][j-1]){
a[i][j]=a[i][j-1];
}else{
a[i][j]=++xx;
}
if(i>1&&c[i-1][j]){
b[i][j]=b[i-1][j];
}else{
b[i][j]=++yy;
}
}
}
}
foru(i,1,n){
foru(j,1,m){
if(c[i][j]){
add_e(a[i][j],b[i][j]+xx+1);
add_e(b[i][j]+xx+1,a[i][j]);
}
}
}
foru(i,1,xx){
memset(vis,0,sizeof vis);
if(find(i)){
ans++;
}
}
cout<<ans;
return 0;
}