pku1736 恶心的插头DP,终于被搞定了。括号匹配法+hash+四进制

一个网格图上某些格子是不能到达了,求从左下角到右下角哈密顿路的数量。
研究了大牛的论文好久,终于写出了这道题目
首先将哈密顿路径改造成哈密顿回路,这样就可以用联通性DP来求得路径数量。
大概方法间论文http://www.cppblog.com/Files/yzhw/dp.doc
下面我说点细节部分
首先是行末的转移,最后一个轮廓线不能有右插头,并且需要将状态右移
举例来说
假设行末的状态为()..().,竖着的轮廓线在最后一个格子的右侧
下行第一个格子的状态即为.()..(),竖着的轮廓线在第一个格子的左侧
自认为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==0break;
 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==0continue;
 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 


posted on 2010-10-31 22:27 yzhw 阅读(985) 评论(1)  编辑 收藏 引用 所属分类: DP

评论

# re: pku1736 恶心的插头DP,终于被搞定了。括号匹配法+hash+四进制 2010-10-31 22:53 yzhw

然后就是障碍格子的处理,要求轮廓线上与障碍格子有关系的2个插头必须为空  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜