由于只能向下走，这样路线就不可能达成一个环，而且又鉴于每个点只能到达一遍，每一次的代价只存在于重设出发点，于是很容易的就想到了最小路径覆盖，赤果果的网络流。把每个节点拆成两个，i入和i出。如果i可以到达j，那么就连一条i出到j入的边，再由源向每一个出连一条边，由入向汇连一条边。上述边的流量都为1。答案就是总的点数减最大流。当然这道题也可以用匈牙利算法做。
program p03;
type
bian=record
next,point,f:longint;
end;
var
b:array[0..5000000] of bian;
p,dst,s:array[0..500000] of longint;
pd:array[0..500000] of boolean;
bo:array[1..600,1..600] of boolean;
tot,len,i,j,n,m,r,c:longint;
ch:char;
procedure getchar(var ch:char);
begin
read(ch);
while (ch<>'.') and (ch<>'x')do
read(ch);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function change(k1,k2:longint):longint;
var
i,j,k,num:longint;
begin
if (k1=n*m*2+1) or (k2=0) then exit(k2);
num:=0;
i:=p[k1];
while i<>-1 do begin
j:=b[i].point;
if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
k:=change(j,min(k2,b[i].f));
k2:=k2-k; num:=num+k;
dec(b[i].f,k); inc(b[i xor 1].f,k);
if k2=0 then break;
end;
i:=b[i].next;
end;
if num=0 then dst[k1]:=-1;
exit(num);
end;
function bfs:boolean;
var
i,j,head,now:longint;
begin
fillchar(dst,sizeof(dst),-1);
fillchar(pd,sizeof(pd),false);
head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
while head>now do begin
inc(now);
i:=p[s[now]];
while i<>-1 do begin
j:=b[i].point;
if (pd[j]=false) and (b[i].f>0) then begin
dst[j]:=dst[s[now]]+1;
pd[j]:=true;
if j=n*m*2+1 then exit(true);
inc(head);
s[head]:=j;
end;
i:=b[i].next;
end;
end;
exit(pd[n*m*2+1]);
end;
procedure ade(k1,k2,k3:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
p[k1]:=len;
end;
procedure add(k1,k2,k3:longint);
begin
ade(k1,k2,k3);
ade(k2,k1,0);
end;
function dinic:longint;
var
num:longint;
begin
num:=0;
while bfs=true do
num:=num+change(0,maxlongint);
exit(num);
end;
begin
readln(n,m,r,c);
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
len:=-1;
for i:=1 to n do
for j:=1 to m do begin
getchar(ch);
if ch='.' then bo[i,j]:=true else bo[i,j]:=false;
end;
for i:=1 to n do
for j:=1 to m do begin
if (i+c<=n) and (j+r<=m) and (bo[i,j]=true) and (bo[i+c,j+r]=true) then
add(i*m+j-m,(i+c)*m-m+j+r+n*m,1);
if (i+r<=n) and (j+c<=m) and (bo[i,j]=true) and (bo[i+r,j+c]=true) then
add(i*m+j-m,(i+r)*m-m+j+c+n*m,1);
if (i+c<=n) and (j-r>0) and (bo[i,j]=true) and (bo[i+c,j-r]=true) then
add(i*m+j-m,(i+c)*m-m+j-r+n*m,1);
if (i+r<=n) and (j-c>0) and (bo[i,j]=true) and (bo[i+r,j-c]=true) then
add(i*m+j-m,(i+r)*m-m+j-c+n*m,1);
end;
tot:=0;
for i:=1 to n do
for j:=1 to m do
if bo[i,j]=true then begin
inc(tot);
add(0,i*m-m+j,1);
add(i*m-m+j+n*m,n*m*2+1,1);
end;
writeln(tot-dinic);
end.
