这是一个比较经典的网络流的建模。
首先我们可以横着和竖着给原图编两遍号，能够一次照到的编号相同。
以样例一为例：
. . .
. # .
. . .
先横着编号：
1 1 1
2 # 3
4 4 4
再竖着编号：
5 6 8
5 # 8
5 7 8
然后我们将横着的图连源点，竖着的图连汇点，横着的与竖着的之间编号相对位置对应的也要连边，即 \(1\) 连 \(5\)，\(2\) 连 \(6\)，\(3\) 连 \(7\)，\(4\) 连 \(8\)，然后直接跑一边最大流即可。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int INF=0x7f7f7f7f;
// char buf[1<<21],*p1=buf,*p2=buf;
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
struct edge
{
int to,nxt,flow;
}e[MAXN<<1];
int head[MAXN],cnt=1;
inline void add(int x,int y,int f)
{
e[++cnt].to=y;
e[cnt].flow=f;
e[cnt].nxt=head[x];
head[x]=cnt;
return;
}
inline void addn(int x,int y,int f)
{
add(x,y,f);
add(y,x,0);
return;
}
int dep[MAXN],gap[MAXN];
int n,m,s,t;
inline void bfs()
{
queue<int>q;
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
dep[t]=1;
gap[1]=1;
q.push(t);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(dep[y]) continue;
q.push(y);
dep[y]=dep[x]+1;
gap[dep[y]]++;
}
}
return;
}
int maxflow,cur[MAXN];
inline int dfs(int x,int flow)
{
if(x==t)
{
maxflow+=flow;
return flow;
}
int used=0;
for(int i=cur[x];i;i=e[i].nxt)
{
cur[x]=i;
int y=e[i].to,f=e[i].flow;
if(dep[x]==dep[y]+1 && f)
{
int w=dfs(y,min(f,flow-used));
e[i].flow-=w;
e[i^1].flow+=w;
used+=w;
if(used==flow) return used;
}
}
gap[dep[x]]--;
if(!gap[dep[x]]) dep[s]=n*m*2+3;
dep[x]++,gap[dep[x]]++;
return used;
}
inline int Isap()
{
maxflow=0;
bfs();
while(dep[s]<=n*m*2+1)
memcpy(cur,head,sizeof(cur)),dfs(s,INF);
return maxflow;
}
char c[305][305];
int id1[305][305],id2[305][305];
int main()
{
n=read(),m=read();
s=0,t=n*m*2+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j];
int tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(c[i][j]=='#') continue;
id1[i][j]=++tot;
int k=j+1;
while(c[i][k]=='.') id1[i][k]=tot,k++;
j=k;
}
int mid=tot;
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
{
if(c[i][j]=='#') continue;
id2[i][j]=++tot;
int k=i+1;
while(c[k][j]=='.') id2[k][j]=tot,k++;
i=k;
}
for(int i=1;i<=mid;i++) addn(s,i,1);
for(int i=mid+1;i<=tot;i++) addn(i,t,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
addn(id1[i][j],id2[i][j],1);
printf("%d\n",Isap());
return 0;
}