1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N = 3e4 + 10;
const int M = 3e5 + 10;
int cnt = 1;
int head[N];
int n, m;
int s, t;
int now[N];
int dep[N];
struct edge {
int u, v, c, val, nxt;
edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0): u(u), v(v), c(c), val(val), nxt(nxt) {}
} e[M];
void ADD(int u, int v, int c, int val) {
cnt++;
e[cnt] = edge(u, v, c, val, head[u]);
head[u] = cnt;
}
void add_edge(int u, int v, int c, int val) {
ADD(u, v, c, val);
ADD(v, u, 0, -val);
}
bool bfs() {
queue<int>q;
memset(dep, 0, sizeof dep);
memcpy(now, head, sizeof head);
dep[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=0) continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[t]!=0;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
int nowflow=0;
for(int i=now[u];i&&nowflow<flow;i=e[i].nxt){
now[u]=i;
int v=e[i].v;
int c=e[i].c;
if(!c||dep[v]!=dep[u]+1)continue;
int ff=dfs(v,t,min(flow-nowflow,c));
if(ff) nowflow+=ff,e[i].c-=ff,e[i^1].c+=ff;
}
return nowflow;
}
int maxflow(){
int ans=0;
while(bfs()){
int nowflow;
while((nowflow=dfs(s,t,inf))) ans+=nowflow;
}
return ans;
}
int r, c;
int dx[4];
int dy[4];
int mp[55][55];
int tot;
int main()
{
cin>>n>>m>>r>>c;
int sum=0;
s=n*m*2+1,t=s+1;
dx[0]=r,dx[1]=c,dx[2]=r,dx[3]=c;
dy[0]=-c,dy[1]=-r,dy[2]=c,dy[3]=r;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char cc;
cin>>cc;
if(cc=='.'){
mp[i][j]=++tot;
sum++;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!mp[i][j])continue;
add_edge(s,mp[i][j],1,0);
add_edge(mp[i][j]+n*m,t,1,0);
for(int k=0;k<4;k++){
int x=i+dx[k],y=j+dy[k];
if(x<1||y<1||x>n||y>m||mp[x][y]==0)continue;
add_edge(mp[i][j],mp[x][y]+n*m,1,0);
}
}
}
cout<<sum-maxflow();
}
|