GDKOI 2015 Day1 T2 单词统计

program wordcount;
const x1:array[1..8] of longint=(-1,-1,-1,0,1,1,1,0);
      y1:array[1..8] of longint=(-1,0,1,1,1,0,-1,-1);
var n,m,x,y,i,j,k,ans,z,nn,t,c,l,h,h2,head,tail:longint;
var s:ansistring;
var mat:array[1..510,1..510] of char;
var q:array[0..10000] of longint;
var flow:array[0..510,0..510] of longint;
var dis:array[0..510] of longint;
function hh(i,j:longint):longint;
begin
  exit((i-1)*2*m+j*2);
end;
function dfs(x,xx:longint):longint;
var i,k:longint;
begin
  if x=nn then exit(xx);
  for i:=0 to nn do
    if (flow[x,i]>0) and (dis[i]=dis[x]+1) then
    begin
      if flow[x,i]>xx then k:=dfs(i,xx) else k:=dfs(i,flow[x,i]);
      dec(flow[x,i],k);
      inc(flow[i,x],k);
      if k>0 then exit(k);
    end;
  exit(0);
end;
procedure bfs;
var i,now:longint;
begin
  fillchar(dis,sizeof(dis),0);
  fillchar(q,sizeof(q),0);
  dis[0]:=1;
  head:=1;
  tail:=1;
  q[1]:=0;
  repeat
    now:=q[head];
    for i:=0 to nn do
      if (flow[now,i]>0) and (dis[i]=0) then
      begin
        dis[i]:=dis[now]+1;
        inc(tail);
        q[tail]:=i;
      end;
    inc(head);
  until head>tail;
end;
begin
  assign(input,‘a.in‘);reset(input);
  assign(output,‘c.out‘);rewrite(output);
  read(t);
  for k:=1 to t do
  begin
    fillchar(q,sizeof(q),0);
    fillchar(flow,sizeof(flow),0);
    fillchar(dis,sizeof(dis),0);
    for i:=1 to 210 do
      for j:=1 to 210 do mat[i,j]:=chr(0);
    readln(n,m);nn:=n*m*2+1;
    for i:=1 to n do
    begin
      readln(s);
      for j:=1 to m do mat[i,j]:=s[j];
    end;
    for i:=1 to n do
      for j:=1 to m do
        begin
          read(c);
          flow[hh(i,j)-1,hh(i,j)]:=c;
        end;
    readln;
    readln(s);
    for i:=1 to n do
      for j:=1 to m do
      begin
        if mat[i,j]=s[1] then flow[0,hh(i,j)-1]:=maxlongint;
        if mat[i,j]=s[length(s)] then flow[hh(i,j),nn]:=maxlongint;
        h2:=pos(mat[i,j],s);
        //if (h2>1) and (h2<length(s)) then
        begin
          for l:=1 to 8 do
          begin
            if (mat[i+x1[l],j+y1[l]]=s[h2+1]) then
              flow[hh(i,j),hh(i+x1[l],j+y1[l])-1]:=maxlongint;
            if (mat[i+x1[l],j+y1[l]]=s[h2-1]) then
              flow[hh(i+x1[l],j+y1[l]),hh(i,j)-1]:=maxlongint;
            end;
          end;
        end;
    //for i:=0 to nn+1 do
      //for j:=0 to nn+1 do if flow[i,j]<>0 then writeln(i,‘ ‘,j,‘ ‘,flow[i,j]);
    ans:=0;
    while 1=1 do
    begin
      bfs;
      if dis[nn]=0 then break;
      repeat
        z:=dfs(0,maxlongint);
        //writeln(z);
        inc(ans,z);
      until z>0;
    end;
    writeln(‘Case #‘,k,‘: ‘,ans);
  end;
  close(input);close(output);
end.