Ural1519 Formula 1（poj 1814）
【问题描述】
一个 m * n 的棋盘，有的格子存在障碍，求经过所有非障碍格子的哈密顿回路个数。
m，n<=12
【分析】
这个是在cdq的ppt《基于连通性状态压缩的动态规划》里的。 可以好好研究一下。
这题也算是状压的入门题了。
【代码】
1 /************************************************************** 2 Problem: 1814 3 User: N_C_Derek 4 Language: Pascal 5 Result: Accepted 6 Time:784 ms 7 Memory:62728 kb 8 ****************************************************************/ 9 10 type node=record 11 v:int64; 12 opt:longint; 13 end; 14 var i,j,n,m,k,l,now,opt,t1,t2,tmp,last:longint; 15 pow:array[0..14]of longint; 16 f:array[0..1,0..1600000]of node; 17 pos:array[0..1,0..1600000]of longint; 18 t:array[0..1]of longint; 19 map:array[0..15,0..15]of boolean; 20 ch:char; 21 function get(opt:longint;v:int64):longint; 22 begin 23 exit(opt div pow[v-1]mod 3); 24 end; 25 function modify(opt,v,k:longint):longint; 26 begin 27 exit(opt+(k-get(opt,v))*pow[v-1]); 28 end; 29 procedure update(opt:longint;k:int64); 30 begin 31 if (j=m)and(opt div pow[m]<>0) then exit; 32 if pos[now,opt]=0 then 33 begin 34 inc(t[now]); 35 pos[now,opt]:=t[now]; 36 f[now,t[now]].v:=k; 37 f[now,t[now]].opt:=opt; 38 end 39 else inc(f[now,pos[now,opt]].v,k); 40 end; 41 function rightchange(opt,k:longint):longint; 42 var i,j,l:longint; 43 begin 44 l:=0; 45 for i:=k+1 to m do 46 begin 47 if get(opt,i)=1 then dec(l) 48 else if get(opt,i)=2 then inc(l); 49 if l=1 then exit(modify(opt,i,1)); 50 end; 51 end; 52 function leftchange(opt,k:longint):longint; 53 var i,l:longint; 54 begin 55 l:=0; 56 for i:=k-1 downto 1 do 57 begin 58 if get(opt,i)=1 then dec(l) 59 else if get(opt,i)=2 then inc(l); 60 if l=-1 then exit(modify(opt,i,2)); 61 end; 62 end; 63 begin 64 readln(n,m); 65 last:=0; 66 for i:=1 to n do 67 begin 68 for j:=1 to m do 69 begin 70 read(ch); 71 if ch='.' then map[i,j]:=true else map[i,j]:=false; 72 if ch='.' then last:=i*m+j; 73 end; 74 readln; 75 end; 76 pow[0]:=1; 77 for i:=1 to m+1 do pow[i]:=pow[i-1]*3; 78 79 80 update(0,1); 81 now:=1-now; 82 for i:=1 to n do 83 for j:=1 to m do 84 begin 85 for k:=1 to t[1-now] do 86 begin 87 opt:=f[1-now,k].opt; 88 t1:=get(opt,m+1);t2:=get(opt,j); 89 if not map[i,j] then 90 begin 91 if (t1=0)and(t2=0) then update(opt,f[1-now,k].v); 92 continue; 93 end; 94 95 if (t1=0)and(t2=0) then 96 begin 97 tmp:=modify(modify(opt,j,1),m+1,2); 98 update(tmp,f[1-now,k].v); 99 end 100 101 else if (t1=t2) then 102 begin 103 if t1=1 then tmp:=rightchange(opt,j) 104 else tmp:=leftchange(opt,j); 105 tmp:=modify(tmp,j,0); 106 tmp:=modify(tmp,m+1,0); 107 update(tmp,f[1-now,k].v); 108 end 109 110 else if (t1=2)and(t2=1) then 111 begin 112 tmp:=modify(modify(opt,j,0),m+1,0); 113 update(tmp,f[1-now,k].v); 114 end 115 116 else if (t1=1)and(t2=2)then begin 117 if i*m+j=last then 118 begin 119 tmp:=modify(modify(opt,j,0),m+1,0); 120 if tmp=0 then update(tmp,f[1-now,k].v); 121 end; 122 end 123 124 else if (t1=0)or(t2=0) then begin 125 tmp:=modify(modify(opt,j,t1+t2),m+1,0); 126 update(tmp,f[1-now,k].v); 127 tmp:=modify(modify(opt,m+1,t1+t2),j,0); 128 update(tmp,f[1-now,k].v); 129 end; 130 131 end; 132 now:=1-now; 133 for l:=1 to t[now] do pos[now,f[now,l].opt]:=0; 134 t[now]:=0; 135 end; 136 writeln(f[1-now,pos[1-now,0]].v); 137 end.