1050 棋盘染色 2 - Wikioi

  1 const
  2     maxn=102;
  3 type
  4     node=record
  5       x,y:longint;
  6     end;
  7     aa=array[0..5]of longint;
  8 var
  9     f:array[0..maxn,0..1204]of longint;
 10     a:array[0..maxn]of longint;
 11     n:longint;
 12 
 13 procedure init;
 14 var
 15     i,j:longint;
 16     s:char;
 17 begin
 18     readln(n);
 19     for i:=1 to n do
 20       begin
 21         for j:=1 to 5 do
 22           begin
 23             read(s);
 24             a[i]:=a[i]<<1+ord(s)-ord(‘0‘);
 25           end;
 26         readln;
 27       end;
 28     while n>0 do
 29       begin
 30         if a[n]>0 then break;
 31         dec(n);
 32       end;
 33     if n=0 then
 34     begin
 35       write(0);
 36       halt;
 37     end;
 38 end;
 39 
 40 procedure get(var a:aa);
 41 var
 42     i,j,k,c:longint;
 43 begin
 44     c:=1;
 45     for i:=1 to 3 do
 46       for j:=1 to 5 do
 47         if a[j]=i then
 48         begin
 49           if i=c then inc(c);
 50           k:=j;
 51           while (k>1) and (a[k-1]>0) do
 52             begin
 53               dec(k);
 54               a[k]:=i;
 55             end;
 56           k:=j;
 57           while (k<5) and (a[k+1]>0) do
 58             begin
 59               inc(k);
 60               a[k]:=i;
 61             end;
 62         end;
 63     dec(c);
 64     for i:=1 to 5 do
 65       if a[i]=4 then
 66       begin
 67         if a[i-1]>0 then a[i]:=c
 68         else
 69           begin
 70              inc(c);
 71              a[i]:=c;
 72           end;
 73       end;
 74 end;
 75 
 76 function bit(x:longint):longint;
 77 begin
 78     if x=0 then exit(0);
 79     exit(bit(x-(x and -x))+1);
 80 end;
 81 
 82 var
 83     q:array[0..maxn*1024]of node;
 84 
 85 procedure work;
 86 var
 87     head,tail,i,j,k,ans,save:longint;
 88     s,t:aa;
 89     flag:boolean;
 90 begin
 91     fillchar(f,sizeof(f),1);
 92     t[0]:=0;
 93     ans:=500;
 94     f[0,0]:=0;
 95     q[1].x:=0;
 96     q[1].y:=0;
 97     head:=1;
 98     tail:=1;
 99     while head<=tail do
100       begin
101         save:=q[head].y;
102         for i:=1 to 5 do
103           begin
104             s[i]:=q[head].y and 3;
105             q[head].y:=q[head].y>>2;
106           end;
107         q[head].y:=save;
108         if q[head].x=n then
109         begin
110           flag:=true;
111           for i:=1 to 5 do
112             if s[i]>1 then flag:=false;
113           if flag then
114           if ans>f[q[head].x,q[head].y] then ans:=f[q[head].x,q[head].y];
115           inc(head);
116           continue;
117         end;
118         for i:=0 to 31 do
119           if i and a[q[head].x+1]=0 then
120           begin
121             for j:=1 to 5 do
122               t[j]:=(((a[q[head].x+1]+i)>>(j-1))and 1)*4;
123             k:=0;
124             for j:=1 to 5 do
125               if (s[j]>0) and (t[j]>0) then
126               begin
127                 t[j]:=s[j];
128                 k:=k or (1<<s[j]);
129               end;
130             flag:=true;
131             for j:=1 to 5 do
132               if (s[j]>0) and (k and (1<<s[j])=0) then flag:=false;
133             if flag=false then continue;
134             get(t);
135             k:=0;
136             for j:=5 downto 1 do
137               k:=k<<2+t[j];
138             if f[q[head].x+1,k]>500 then
139             begin
140               inc(tail);
141               q[tail].x:=q[head].x+1;
142               q[tail].y:=k;
143             end;
144             if f[q[head].x+1,k]>f[q[head].x,q[head].y]+bit(i) then f[q[head].x+1,k]:=f[q[head].x,q[head].y]+bit(i);
145           end;
146         inc(head);
147       end;
148     write(ans);
149 end;
150 
151 begin
152     init;
153     work;
154 end.