一個(gè)網(wǎng)格圖上某些格子是不能到達(dá)了，求從左下角到右下角哈密頓路的數(shù)量。
研究了大牛的論文好久，終于寫出了這道題目
首先將哈密頓路徑改造成哈密頓回路，這樣就可以用聯(lián)通性DP來求得路徑數(shù)量。
大概方法間論文
http://www.shnenglu.com/Files/yzhw/dp.doc下面我說點(diǎn)細(xì)節(jié)部分
首先是行末的轉(zhuǎn)移，最后一個(gè)輪廓線不能有右插頭，并且需要將狀態(tài)右移
舉例來說
假設(shè)行末的狀態(tài)為()..().，豎著的輪廓線在最后一個(gè)格子的右側(cè)
下行第一個(gè)格子的狀態(tài)即為.()..()，豎著的輪廓線在第一個(gè)格子的左側(cè)
自認(rèn)為java跑了500ms還算快的了～
1 import java.util.*;
2 import java.util.Map.Entry;
3 import java.io.*;
4 public class Main {
5
6 /**
7 * @param args
8 */
9 static int r=0,c=0;
10 static String map[]=new String[10];
11 static HashMap<Integer,Integer> dp[][]=new HashMap[10][2];
12 static final int encode(int code[])
13 {
14 int res=0;
15 for(int i=0;i<code.length;i++)
16 {
17 res<<=2;
18 res|=code[i];
19 }
20 return res;
21 }
22 static final void decode(int code[],int cd)
23 {
24 for(int i=code.length-1;i>=0;i--)
25 {
26 code[i]=cd&3;
27 cd>>=2;
28 }
29 }
30 static void print(int i,int j,int code[],int num)
31 {
32 /* System.out.print("row="+i+" col="+j+" code=");
33 for(int k=0;k<code.length;k++)
34 System.out.print(code[k]+" ");
35 System.out.println(num);*/
36 }
37 public static void main(String[] args) throws IOException{
38 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
39 for(int i=0;i<10;i++)
40 for(int j=0;j<2;j++)
41 dp[i][j]=new HashMap<Integer,Integer>();
42 while(true)
43 {
44 String tmp[]=in.readLine().split(" ");
45 r=Integer.parseInt(tmp[0]);
46 c=Integer.parseInt(tmp[1]);
47 if(r==0&&c==0) break;
48 map[0]="";
49 for(int i=0;i<c+4;i++)
50 map[0]+='.';
51 map[1]=".";
52 for(int i=0;i<c+2;i++)
53 map[1]+='#';
54 map[1]+='.';
55 for(int i=2;i<2+r;i++)
56 {
57 map[i]=in.readLine();
58 if(i!=1+r) map[i]=".#"+map[i]+"#.";
59 else map[i]=".."+map[i]+"..";
60 }
61 c+=4;
62 r+=2;
63 int last=0;
64 // for(int i=0;i<r;i++)
65 // System.out.println(map[i]);
66 // System.out.println();
67 dp[0][0].clear();
68 int code[]=new int[r+1];
69 code[0]=1;
70 code[1]=2;
71 dp[0][0].put(encode(code), 1);
72 for(int j=0;j<c;j++)
73 for(int i=0;i<r;i++)
74 {
75 if(i==0&&j==0) continue;
76 dp[i][j&1].clear();
77 int p1=(i==0?r-1:i-1),p2=(i==0?j-1:j);
78 for(Entry<Integer, Integer> p:dp[p1][p2&1].entrySet())
79 {
80 decode(code,p.getKey());
81 print(p1,p2,code,p.getValue());
82 if(map[i].charAt(j)=='.')
83 {
84 last=i*c+j;
85 if(i==r-1)
86 {
87 if(code[i]==2&&code[i+1]==1||i==r-1&&j==c-1&&code[i]==1&&code[i+1]==2)
88 {
89 code[i]=0;
90 code[i+1]=0;
91 if(dp[i][j&1].containsKey(encode(code)>>2))
92 dp[i][j&1].put(encode(code)>>2, dp[i][j&1].get(encode(code)>>2)+p.getValue());
93 else
94 dp[i][j&1].put(encode(code)>>2, p.getValue());
95 }
96 else if(code[i]==0&&code[i+1]!=0||code[i+1]==0&&code[i]!=0)
97 {
98 code[i]=(code[i]!=0?code[i]:code[i+1]);
99 code[i+1]=0;
100 if(dp[i][j&1].containsKey(encode(code)>>2))
101 dp[i][j&1].put(encode(code)>>2, dp[i][j&1].get(encode(code)>>2)+p.getValue());
102 else
103 dp[i][j&1].put(encode(code)>>2, p.getValue());
104 }
105 else if(code[i]==2&&code[i+1]==2)
106 {
107 int t=0;
108 code[i]=code[i+1]=0;
109 for(int k=i-1;k>=0;k--)
110 {
111 if(code[k]==1) t++;
112 else if(code[k]==2) t--;
113 if(t==1)
114 {
115 code[k]=2;
116 break;
117 }
118 }
119 if(dp[i][j&1].containsKey(encode(code)>>2))
120 dp[i][j&1].put(encode(code)>>2, dp[i][j&1].get(encode(code)>>2)+p.getValue());
121 else
122 dp[i][j&1].put(encode(code)>>2, p.getValue());
123 }
124 }
125 else
126 {
127 if(code[i]==0&&code[i+1]==0)
128 {
129 code[i]=1;
130 code[i+1]=2;
131 if(dp[i][j&1].containsKey(encode(code)))
132 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
133 else
134 dp[i][j&1].put(encode(code), p.getValue());
135 }
136 else if(code[i]==2&&code[i+1]==1||i==r-1&&j==c-1&&code[i]==1&&code[i+1]==2)
137 {
138 code[i]=code[i+1]=0;
139 if(dp[i][j&1].containsKey(encode(code)))
140 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
141 else
142 dp[i][j&1].put(encode(code), p.getValue());
143 }
144 else if(code[i]==0||code[i+1]==0)
145 {
146 if(dp[i][j&1].containsKey(encode(code)))
147 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
148 else
149 dp[i][j&1].put(encode(code), p.getValue());
150 int t=code[i];
151 code[i]=code[i+1];
152 code[i+1]=t;
153 if(dp[i][j&1].containsKey(encode(code)))
154 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
155 else
156 dp[i][j&1].put(encode(code), p.getValue());
157 }
158 else if(code[i]==1&&code[i+1]==1)
159 {
160 int t=0;
161 code[i]=code[i+1]=0;
162 for(int k=i+2;k<code.length;k++)
163 {
164 if(code[k]==1) t++;
165 else if(code[k]==2) t--;
166 if(t==-1)
167 {
168 code[k]=1;
169 break;
170 }
171 }
172 if(dp[i][j&1].containsKey(encode(code)))
173 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
174 else
175 dp[i][j&1].put(encode(code), p.getValue());
176 }
177 else if(code[i]==2&&code[i+1]==2)
178 {
179 int t=0;
180 code[i]=code[i+1]=0;
181 for(int k=i-1;k>=0;k--)
182 {
183 if(code[k]==1) t++;
184 else if(code[k]==2) t--;
185 if(t==1)
186 {
187 code[k]=2;
188 break;
189 }
190 }
191 if(dp[i][j&1].containsKey(encode(code)))
192 dp[i][j&1].put(encode(code), dp[i][j&1].get(encode(code))+p.getValue());
193 else
194 dp[i][j&1].put(encode(code), p.getValue());
195 }
196 }
197 }
198 else
199 {
200 if(code[i]==0&&code[i+1]==0)
201 if(i==r-1)
202 {
203 if(code[i]==0&&code[i+1]==0)
204 if(dp[i][j&1].containsKey(p.getKey()>>2))
205 dp[i][j&1].put(p.getKey()>>2, dp[i][j&1].get(p.getKey()>>2)+p.getValue());
206 else
207 dp[i][j&1].put(p.getKey()>>2, p.getValue());
208 }
209 else
210 {
211 if(code[i]==0&&code[i+1]==0)
212 if(dp[i][j&1].containsKey(p.getKey()))
213 dp[i][j&1].put(p.getKey(), dp[i][j&1].get(p.getKey())+p.getValue());
214 else
215 dp[i][j&1].put(p.getKey(), p.getValue());
216 }
217 }
218 }
219 }
220 if(last==(r-1)*c+c-1)
221 System.out.println(dp[r-1][(c-1)&1].containsKey(0)?dp[r-1][(c-1)&1].get(0):0);
222 else
223 System.out.println(0);
224 }
225
226 }
227
228 }
229