整个矿区中存在A矿，B矿，C矿三个矿场，和a厂，b厂，c厂三个炼矿厂。每个三角形的区域可以是一个矿场、炼矿厂、山地、或者平地。现在矿区管理局要求建立一个交通系统，使得矿场和对应炼矿厂之间存在一条公路，并且三条公路互不交叉(即一个三角形区域中不存在两条以上运输不同矿的公路)。两个三角形区域是相邻的当且仅当这两个三角形存在公共边，只有相邻的两个区域之间才能建一段路，建这段路的费用为1。注意，山地上是不能建公路的。由于火星金融危机的影响，矿区管理局想知道建立这样一个交通系统最少要花多少费用。更多的，当局向知道有多少种花费最小的方案。
第1行一个整数N。表示这个矿区是边长为N的正六边形。
接下来有6*N*N的整数，分为2*N行，表示矿区当前区域的情况。0表示平地，1,2,3表示对应的矿区或者炼矿厂，4表示山地。（样例1对应图2）。可能有多组数据，请处理到文件结尾
对于每组数据，包含两个整数，表示最小费用和达到最小费用的方案数。如果找不到符合要求的方案，输出-1 -1。由于方案数可能过大，所以请把方案数mod 1000000007
对于100%的数据，N≤6
1 const ss=9875321;
2 const mo=1000000007;
3 const nn=10000000;
4 var
5 b:array[0..15,0..25]of longint;
6 a:array[0..15,0..25,0..3,0..3,0..3,0..3]of boolean;
7 ax:array[0..15,0..25,0..3,0..3,0..3,0..3]of longint;
8 d:array[0..nn]of longint;
9 g:array[0..ss,0..1]of longint;
10 next,u:array[0..nn,0..1]of longint;
11 f,w:array[0..nn,0..1]of longint;
12 e:array[0..nn,0..1]of boolean;
13 l,r,kk,qq,sx,sy,ii,jj,t1,t2,tt,i,j,n,m,k,t,x,y,z,p,q:longint;
14 procedure o(p,k,q,t:longint);
15 begin
16 ax[i,j,p,q,k,t]:=0;
17 if (b[i+1,j]<>0)and(k<>b[i+1,j])and(k<>0) then exit;
18 if (b[i,j+1]<>0)and(t<>b[i,j+1])and(t<>0) then exit;
19 a[i,j,p,q,k,t]:=true;
20 if (p+k>0)or((x>0)and(x<4)) then inc(ax[i,j,p,q,k,t]);
21 if (q+t>0)or((y>0)and(y<4)) then inc(ax[i,j,p,q,k,t]);
22 end;
23 function hash(x,t:longint):longint;
24 var i:longint;
25 begin
26 if t=tt then
27 begin
28 i:=x mod ss+1;
29 if u[g[i,t],t]=x then begin hash:=g[i,t]; g[i,t]:=next[g[i,t],t]; exit; end;
30 i:=g[i,t];
31 while u[next[i,t],t]<>x do i:=next[i,t];
32 hash:=next[i,t];
33 next[i,t]:=next[next[i,t],t]; exit;
34 end;
35 i:=g[x mod ss+1,t];
36 while (i<>0)and(u[i,t]<>x) do i:=next[i,t];
37 if u[i,t]=x then exit(i);
38 inc(t2); i:=x mod ss+1; u[t2,t]:=x;
39 next[t2,t]:=g[i,t]; g[i,t]:=t2; exit(t2);
40 end;
41 begin
42 while true do
43 begin
44 fillchar(a,sizeof(a),0);
45 fillchar(b,sizeof(b),0);
46 fillchar(ax,sizeof(ax),0);
47 readln(n); if eof then exit;
48 x:=n*2+1; m:=n*4;
49 u[0,0]:=-1; u[0,1]:=-1;
50 for i:=0 to n+n+1 do
51 for j:=0 to m+1 do b[i,j]:=4;
52 for i:=1 to n do
53 begin
54 for j:=1 to x do read(b[i,j]);
55 x:=x+2;
56 end;
57 for i:=n+1 to n+n do
58 begin
59 x:=x-2;
60 for j:=m-x+1 to m do read(b[i,j]);
61 end; n:=n*2; readln;
62 for i:=1 to n do
63 for j:=1 to m do
64 if j and 1=0 then
65 begin
66 x:=b[i,j-1]; y:=b[i,j];
67 if (x=0)and(y=0) then
68 begin
69 for p:=0 to 3 do begin o(0,0,p,p); o(0,p,p,0); o(0,p,0,p); o(p,0,0,p); o(p,0,p,0); o(p,p,0,0); end;
70 for p:=1 to 3 do for q:=1 to 3 do o(p,p,q,q);
71 end else
72 if (x=0)and(y<>4) then
73 begin
74 for p:=0 to 3 do begin o(p,p,y,0); o(p,p,0,y); end;
75 o(y,0,0,0); o(0,y,0,0);
76 end else
77 if (x=0)and(y=4) then
78 begin
79 for p:=0 to 3 do o(p,p,0,0);
80 end else
81 if (x<>4)and(y=0) then
82 begin
83 for p:=0 to 3 do begin o(x,0,p,p); o(0,x,p,p); end;
84 o(0,0,x,0); o(0,0,0,x);
85 end else
86 if (x<>4)and(y<>4) then
87 begin
88 o(x,0,y,0); o(x,0,0,y); o(0,x,y,0); o(0,x,0,y);
89 if x=y then o(0,0,0,0);
90 end else
91 if (x<>4)and(y=4) then
92 begin
93 o(x,0,0,0); o(0,x,0,0);
94 end else
95 if (x=4)and(y=0) then
96 begin
97 for p:=0 to 3 do o(0,0,p,p);
98 end else
99 if (x=4)and(y<>4) then
100 begin
101 o(0,0,y,0); o(0,0,0,y);
102 end else o(0,0,0,0);
103 end;
104 for i:=0 to nn do
105 for j:=0 to 1 do f[i,j]:=nn;
106 tt:=1; i:=hash(0,0); tt:=0;
107 f[i,0]:=0; w[i,0]:=1; e[i,0]:=true;
108 l:=1; r:=1; t:=2; p:=1; q:=2; kk:=1; t1:=1; t2:=0;
109 while true do
110 begin
111 while true do
112 begin
113 k:=hash(d[l],tt);
114 if q=2 then d[l]:=d[l]*4;
115 x:=(d[l]>>(q-2))and 3;
116 y:=(d[l]>>q)and 3;
117 sx:=d[l]-x<<(q-2)-y<<q;
118 for ii:=0 to 3 do
119 for jj:=0 to 3 do
120 if a[p,q,x,y,ii,jj] then
121 begin
122 qq:=sx+ii<<(q-2)+jj<<q;
123 z:=hash(qq,kk);
124 if f[z,kk]>f[k,tt]+ax[p,q,x,y,ii,jj] then
125 begin
126 f[z,kk]:=f[k,tt]+ax[p,q,x,y,ii,jj];
127 w[z,kk]:=w[k,tt];
128 if not e[z,kk] then
129 begin
130 e[z,kk]:=true; d[t]:=qq; inc(t);
131 if t=nn then t:=1;
132 end;
133 end else
134 if f[z,kk]=f[k,tt]+ax[p,q,x,y,ii,jj] then
135 begin
136 inc(w[z,kk],w[k,tt]);
137 if w[z,kk]>=mo then dec(w[z,kk],mo);
138 end;
139 end;
140 e[k,tt]:=false; w[k,tt]:=0;
141 f[k,tt]:=nn;
142 if l=r then break;
143 inc(l); if l=nn then l:=1;
144 end;
145 inc(l); if l=nn then l:=1;
146 if l=t then break;
147 if t=1 then r:=nn-1 else r:=t-1; tt:=kk; kk:=1-kk; t1:=t2; t2:=0;
148 if q=m then begin q:=2; inc(p); end else inc(q,2);
149 if p>n then break;
150 end;
151 i:=g[1,tt];
152 while (i<>0)and(u[i,tt]<>0) do i:=next[i,tt];
153 if i=0 then writeln(‘-1 -1‘) else
154 begin
155 writeln(f[i,tt]-3,‘ ‘,w[i,tt]);
156 end;
157 while l<>t do
158 begin
159 k:=hash(d[l],tt);
160 e[k,tt]:=false; w[k,tt]:=0;
161 f[k,tt]:=nn;
162 if l=r then break;
163 inc(l); if l=nn then l:=1;
164 end;
165 end;
166 end.
原文：http://www.cnblogs.com/cyz666/p/6337691.html