URAL1519 Formula 1 —

URAL1519 Formula 1 —— 插头DP

题目链接：https://vjudge.net/problem/URAL-1519

1519. Formula 1

Time limit: 1.0 second
Memory limit: 64 MB

Background

Regardless of the fact, that Vologda could not get rights to hold the Winter Olympic games of 20**, it is well-known, that the city will conduct one of the Formula 1 events. Surely, for such an important thing a new race circuit should be built as well as hotels, restaurants, international airport - everything for Formula 1 fans, who will flood the city soon. But when all the hotels and a half of the restaurants were built, it appeared, that at the site for the future circuit a lot of gophers lived in their holes. Since we like animals very much, ecologists will never allow to build the race circuit over the holes. So now the mayor is sitting sadly in his office and looking at the map of the circuit with all the holes plotted on it.

Problem

Who will be smart enough to draw a plan of the circuit and keep the city from inevitable disgrace? Of course, only true professionals - battle-hardened programmers from the first team of local technical university!.. But our heroes were not looking for easy life and set much more difficult problem: "Certainly, our mayor will be glad, if we find how many ways of building the circuit are there!" - they said.

It should be said, that the circuit in Vologda is going to be rather simple. It will be a rectangle N*M cells in size with a single circuit segment built through each cell. Each segment should be parallel to one of rectangle's sides, so only right-angled bends may be on the circuit. At the picture below two samples are given for N = M = 4 (gray squares mean gopher holes, and the bold black line means the race circuit). There are no other ways to build the circuit here.

Input

The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located. There are at least 4 cells without gopher holes.

Output

You should output the desired number of ways. It is guaranteed, that it does not exceed 263-1.

Samples

input	output
4 4 **.. .... .... ....	2
4 4 .... .... .... ....	6

Problem Author: Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge

Tags: none ()

题意：

用一个回路去走完所有的空格，问有多少种情况？

题解：

1.学习插头DP的必经之路：《基于连通性状态压缩的动态规划问题》

2.HDU1693 Eat the Trees 这题的加强版。

3.相对于HDU1693，由于此题限制了只能用一个回路，所以在处理的时候，需要记录轮廓线上，每个插头分别属于哪个连通分量的，以此避免形成多个回路。

4.由于m<=12，故连通分量最多为12/2 = 6个，再加上没有插头的情况，所以轮廓线上每个位置的状态共有7种，为了加快速度，我们采用8进制对其进行压缩。

5.对于一条轮廓线，最多有：8^(12+1)种状态，所以直接用数组进行存储或者直接枚举所以状态是不可行的。但我们知道其中有许多状态是无效的，所以我们采用哈希表来存在有效状态，即能解决空间有限的问题，还能减少直接枚举所需要的时间花费。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const int INF = 2e9;
 15 const LL LNF = 9e18;
 16 const int MOD = 1e9+7;
 17 const int MAXN = 1e5;
 18 const int HASH = 1e4;
 19 
 20 int n, m, last_x, last_y;
 21 bool maze[13][13];
 22 
 23 struct  //注意哈希表的大小
 24 {
 25     int size, head[HASH], next[MAXN];
 26     LL state[MAXN], sum[MAXN];
 27 
 28     void init()
 29     {
 30         size = 0;
 31         memset(head, -1, sizeof(head));
 32     }
 33 
 34     void insert(LL status, LL Sum)
 35     {
 36         int u = status%HASH;
 37         for(int i = head[u]; i!=-1; i = next[i])
 38         {
 39             if(state[i]==status)
 40             {
 41                 sum[i] += Sum;
 42                 return;
 43             }
 44         }
 45         state[size] = status;   //头插法
 46         sum[size] = Sum;
 47         next[size] = head[u];
 48         head[u] = size++;
 49     }
 50 
 51 }Hash_map[2];
 52 
 53 struct
 54 {
 55     int code[13];   //用于记录轮廓线上每个位置的插头状态
 56     LL encode(int m)    //编码：把轮廓线上的信息压缩到一个longlong类型中
 57     {
 58         LL status = 0;
 59         int id[13], cnt = 0;
 60         memset(id, -1, sizeof(id));
 61         id[0] = 0;
 62         for(int i = m; i>=0; i--)   //从高位到低位。为每个连通块重新编号，采用最小表示法。
 63         {
 64             if(id[code[i]]==-1) id[code[i]] = ++cnt;
 65             code[i] = id[code[i]];
 66             status <<= 3;   //编码
 67             status += code[i];
 68         }
 69         return status;
 70     }
 71 
 72     void decode(int m, LL status)  //解码：将longlong类型中轮廓线上的信息解码到数组中
 73     {
 74         memset(code, 0, sizeof(code));
 75         for(int i = 0; i<=m; i++)   //从低位到高位
 76         {
 77             code[i] = status&7;
 78             status >>= 3;
 79         }
 80     }
 81 
 82     void shift(int m)   //左移：在每次转行的时候都需要执行。
 83     {
 84         for(int i = m-1; i>=0; i--)
 85             code[i+1] = code[i];
 86         code[0] = 0;
 87     }
 88 
 89 }Line;
 90 
 91 void transfer_blank(int i, int j, int cur)
 92 {
 93     for(int k = 0; k<Hash_map[cur].size; k++)   //枚举上一个格子所有合法的状态
 94     {
 95         LL status = Hash_map[cur].state[k]; //得到状态
 96         LL Sum = Hash_map[cur].sum[k];      //得到数量
 97         Line.decode(m, status);             //对状态进行解码
 98         int up = Line.code[j];         //得到上插头
 99         int left = Line.code[j-1];     //得到下插头
100 
101         if(!up && !left)        //没有上、左插头，新建分量
102         {
103             if(maze[i+1][j] && maze[i][j+1])    //如果新建的两个插头所指向的两个格子可行，新建的分量才合法
104             {
105                 Line.code[j] = Line.code[j-1] = 6;  //为新的分量编号，最大的状态才为6
106                 Hash_map[cur^1].insert(Line.encode(m), Sum);
107             }
108         }
109         else if( (left&&!up) || (!left&&up) )   //仅有其中一个插头，延续分量
110         {
111             int line = left?left:up;    //记录是哪一个插头
112             if(maze[i][j+1])    //往右延伸
113             {
114                 Line.code[j-1] = 0;
115                 Line.code[j] = line;
116                 Hash_map[cur^1].insert(Line.encode(m), Sum);
117             }
118             if(maze[i+1][j])        //往下延伸
119             {
120                 Line.code[j-1] = line;
121                 Line.code[j] = 0;
122                 if(j==m) Line.shift(m);
123                 Hash_map[cur^1].insert(Line.encode(m), Sum);
124             }
125         }
126         else    //上、左插头都存在，尝试合并。
127         {
128             if(up!=left)    //如果两个插头属于两个联通分量，那么就合并
129             {
130                 Line.code[j] = Line.code[j-1] = 0;
131                 for(int t = 0; t<=m; t++)   //随便选一个编号最为他们合并后分量的编号
132                     if(Line.code[t]==up)
133                         Line.code[t] = left;
134                 if(j==m) Line.shift(m);
135                 Hash_map[cur^1].insert(Line.encode(m), Sum);
136             }
137             else if(i==last_x && j==last_y) //若两插头同属一个分量，则只能在最后的可行格中合并，否则会出现多个联通分量
138             {
139                 Line.code[j] = Line.code[j-1] = 0;
140                 if(j==m) Line.shift(m);
141                 Hash_map[cur^1].insert(Line.encode(m), Sum);
142             }
143         }
144     }
145 }
146 
147 void transfer_block(int i, int j, int cur)
148 {
149     for(int k = 0; k<Hash_map[cur].size; k++)
150     {
151         LL status = Hash_map[cur].state[k]; //得到状态
152         LL Sum = Hash_map[cur].sum[k];      //得到数量
153         Line.decode(m, status);
154         Line.code[j] = Line.code[j-1] = 0;
155         if(j==m) Line.shift(m);
156         Hash_map[cur^1].insert(Line.encode(m), Sum);
157     }
158 }
159 
160 int main()
161 {
162     char s[15];
163     while(scanf("%d%d", &n, &m)!=EOF)
164     {
165         memset(maze, false, sizeof(maze));
166         for(int i = 1; i<=n; i++)
167         {
168             scanf("%s", s+1);
169             for(int j = 1; j<=m; j++)
170             {
171                 if(s[j]=='.')
172                 {
173                     maze[i][j] = true;
174                     last_x = i;         //记录最后一个可行格
175                     last_y = j;
176                 }
177             }
178         }
179 
180         int cur = 0;
181         Hash_map[cur].init();   //初始化
182         Hash_map[cur].insert(0, 1); //插入初始状态
183         for(int i = 1; i<=n; i++)
184         for(int j = 1; j<=m; j++)
185         {
186             Hash_map[cur^1].init();
187             if(maze[i][j])
188                 transfer_blank(i, j, cur);
189             else
190                 transfer_block(i, j ,cur);
191             cur ^= 1;
192         }
193 
194         LL last_status = 0; //最后的轮廓线就是最后一行，且每个位置都没有插头
195         LL ans = Hash_map[cur].size?Hash_map[cur].sum[last_status]:0;
196         printf("%I64d
", ans);
197     }
198 }

View Code