題目鏈接：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

inputoutput

4 4 **.. .... .... ....	2
4 4 .... .... .... ....	6

Problem Author:?Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source:?Timus Top Coders: Third Challenge Tags:?none ?(hide tags for unsolved problems)

?

?

題意：

用一個(gè)回路去走完所有的空格，問(wèn)有多少種情況？

?

題解：

1.學(xué)習(xí)插頭DP的必經(jīng)之路：《基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問(wèn)題》

2.HDU1693 Eat the Trees?這題的加強(qiáng)版。

3.相對(duì)于HDU1693，由于此題限制了只能用一個(gè)回路，所以在處理的時(shí)候，需要記錄輪廓線上，每個(gè)插頭分別屬于哪個(gè)連通分量的，以此避免形成多個(gè)回路。

4.由于m<=12，故連通分量最多為12/2 = 6個(gè)，再加上沒(méi)有插頭的情況，所以輪廓線上每個(gè)位置的狀態(tài)共有7種，為了加快速度，我們采用8進(jìn)制對(duì)其進(jìn)行壓縮。

5.對(duì)于一條輪廓線，最多有：8^(12+1)種狀態(tài)，所以直接用數(shù)組進(jìn)行存儲(chǔ)或者直接枚舉所以狀態(tài)是不可行的。但我們知道其中有許多狀態(tài)是無(wú)效的，所以我們采用哈希表來(lái)存在有效狀態(tài)，即能解決空間有限的問(wèn)題，還能減少直接枚舉所需要的時(shí)間花費(fèi)。

?

?

代碼如下：

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]; //用于記錄輪廓線上每個(gè)位置的插頭狀態(tài) 56 LL encode(int m) //編碼：把輪廓線上的信息壓縮到一個(gè)longlong類(lèi)型中 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--) //從高位到低位。為每個(gè)連通塊重新編號(hào)，采用最小表示法。 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類(lèi)型中輪廓線上的信息解碼到數(shù)組中 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) //左移：在每次轉(zhuǎn)行的時(shí)候都需要執(zhí)行。 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++) //枚舉上一個(gè)格子所有合法的狀態(tài) 94 { 95 LL status = Hash_map[cur].state[k]; //得到狀態(tài) 96 LL Sum = Hash_map[cur].sum[k]; //得到數(shù)量 97 Line.decode(m, status); //對(duì)狀態(tài)進(jìn)行解碼 98 int up = Line.code[j]; //得到上插頭 99 int left = Line.code[j-1]; //得到下插頭 100 101 if(!up && !left) //沒(méi)有上、左插頭，新建分量 102 { 103 if(maze[i+1][j] && maze[i][j+1]) //如果新建的兩個(gè)插頭所指向的兩個(gè)格子可行，新建的分量才合法 104 { 105 Line.code[j] = Line.code[j-1] = 6; //為新的分量編號(hào)，最大的狀態(tài)才為6 106 Hash_map[cur^1].insert(Line.encode(m), Sum); 107 } 108 } 109 else if( (left&&!up) || (!left&&up) ) //僅有其中一個(gè)插頭，延續(xù)分量 110 { 111 int line = left?left:up; //記錄是哪一個(gè)插頭 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) //如果兩個(gè)插頭屬于兩個(gè)聯(lián)通分量，那么就合并 129 { 130 Line.code[j] = Line.code[j-1] = 0; 131 for(int t = 0; t<=m; t++) //隨便選一個(gè)編號(hào)最為他們合并后分量的編號(hào) 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) //若兩插頭同屬一個(gè)分量，則只能在最后的可行格中合并，否則會(huì)出現(xiàn)多個(gè)聯(lián)通分量 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]; //得到狀態(tài) 152 LL Sum = Hash_map[cur].sum[k]; //得到數(shù)量 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; //記錄最后一個(gè)可行格 175 last_y = j; 176 } 177 } 178 } 179 180 int cur = 0; 181 Hash_map[cur].init(); //初始化 182 Hash_map[cur].insert(0, 1); //插入初始狀態(tài) 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; //最后的輪廓線就是最后一行，且每個(gè)位置都沒(méi)有插頭 195 LL ans = Hash_map[cur].size?Hash_map[cur].sum[last_status]:0; 196 printf("%I64d\n", ans); 197 } 198 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/DOLFAMINGO/p/8004121.html

總結(jié)

以上是生活随笔為你收集整理的URAL1519 Formula 1 —— 插头DP的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。