所有的白格向能攻击到的黑格连单向边，然后最大独立集就行了。细节看代码吧。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 411274 | lbz007 | 3175 | Accepted | 20068 kb | 2212 ms | Pascal/Edit | 1637 B | 2013-05-13 17:19:41 |
1 const 2 x:array[1..8]of longint=(-1,-2,1,2,-1,-2,1,2); 3 y:array[1..8]of longint=(-2,-1,-2,-1,2,1,2,1); 4 var 5 n,i,j,k,numa,ans,ee:longint; 6 b,link,e,head,next:Array[1..1000000]of longint; 7 d,a:Array[1..200,1..200]of longint; 8 c:char; 9 procedure add(u,v:longint); 10 begin 11 inc(ee);next[ee]:=head[u];head[u]:=ee;e[ee]:=v; 12 //inc(ee);next[ee]:=head[v];head[v]:=ee;e[ee]:=u ; 13 end; 14 function find(x:longint):boolean; 15 var j:longint; 16 begin 17 j:=head[x]; 18 while j<>0 do 19 begin 20 if b[e[j]]<>i then 21 begin 22 b[e[j]]:=i; 23 if (link[e[j]]=0) or (find(link[e[j]])) then 24 begin 25 link[e[j]]:=x; 26 exit(true); 27 end; 28 end; 29 j:=next[j]; 30 end; 31 exit(false); 32 end; 33 begin 34 readln(n); 35 for i:=1 to n do 36 begin 37 for j:=1 to n do 38 begin 39 read(c);if c='0' then inc(numa); 40 a[i,j]:=ord(c)-ord('0'); 41 end; 42 readln; 43 end; 44 for i:=1 to n do 45 for j:=1 to n do 46 begin inc(k);d[i,j]:=k;end; 47 for i:=1 to n do 48 for j:=1 to n do 49 if (a[i,j]=0)and((i+j) mod 2=0) then 50 for k:=1 to 8 do 51 if (i+x[k]>0)and(i+x[k]<=n)and(j+y[k]>0)and(j+y[k]<=n)then 52 if a[i+x[k],j+y[k]]=0 then 53 add(d[i,j],d[i+x[k],j+y[k]]); 54 55 for k:=1 to n do 56 for j:=1 to n do 57 if (k+j) mod 2=0 then 58 if a[k,j]=0 then 59 begin 60 i:=d[k,j]; 61 if find(i) then inc(ans); 62 end; 63 writeln(numa-ans); 64 end.