Problem number six. Go ahead, young man
Topic link
Poj.org/problem?id=…
Topic describes
A square township has been divided up into n*m(n rows and m columns) square plots (1<=N,M<=8),some of them are blocked, others are unblocked.
The Farm is located in the lower left plot and the Market is located in the lower right plot.
Tony takes her tour of the township going from Farm to Market by walking through every unblocked plot exactly once.
Write a program that will count how many unique tours Betsy can take in going from Farm to Market.
The title input
The input contains several test cases.
The first line of each test case contain two integer numbers n,m, denoting the number of rows and columns of the farm.
The following n lines each contains m characters, describe the farm. A ‘#’ means a blocked square, a ‘.’ means a unblocked square.
The last test case is followed by two zeros.
The title output
For each test case output the answer on a single line.
The sample input
2 2.. . # 2, 3,.. . 3, 4,... . . 0 0
Sample output
1 1 4
The sample explain
3, 4,... . .
This sample set has four paths:! [] (img – blog. Csdnimg. Cn/img_convert… =100×100)! [] (img – blog. Csdnimg. Cn/img_convert… =100×100)! [] (img – blog. Csdnimg. Cn/img_convert… =100×100)! [] (img – blog. Csdnimg. Cn/img_convert… =100×100)
Their thinking
This problem is the template problem for plug DP. Plug DP generally has three recursion modes:
- I’m going to do it grid by grid
- Recursive line by line
- Per column recursion
I looked at the problem solutions on the Internet, most of them are grid by grid recursion, and use too many optimization techniques, I feel that these problem solutions are not very friendly to beginners. Therefore, this article uses line-by-line recursion and does not use arcane optimizations to help you understand.
Of course, if you want a more detailed, comprehensive, rigorous, scientific explanation, you can read itIOI national Training team member Danqi ChenDynamic Programming Problem based on Connectivity State Compression. How to download the paper is attached at the end of the paper.
You need some knowledge before you study:
- Hamilton path
- Check and set
- State of compression
So let’s talk a little bit about these three points.
Hamilton path
The Hamilton path is a concept in graph theory.
Let G=(V,E)G=(V,E)G=(V,E) G=(V,E)G=(V,E) is a graph. If a path in GGG passes through each vertex only once, it is called a Hamilton path.
In this case, we can think of each ‘.’ as a node of GGG, with an edge between two adjacent ‘.’ corresponding nodes.
So the question becomes, in graph GGG, how many Hamilton paths are there that start at the corresponding node in the lower left and end at the corresponding node in the lower right.
For example, the following set of inputs,
3 3 #.. . . #.
The following graph GGG,! [] (img – blog. Csdnimg. Cn/img_convert… =200×200)
In the figure, the bold red edge identifies a Hamilton path.
Check and set
The search set is a tree data structure, which is generally used to solve the merge and query problems of multiple disjoint sets.
Each set SiS_iSi has a corresponding tree TiT_iTi in the union lookup set. The element in SiS_iSi corresponds to the node in TiT_iTi.
Parallel lookup sets support two operations:
- Find: Finds the root node in the tree of a node.
- Merge: Merges two nodes into one tree. Turning one tree into a subtree of another. One way to do this is to make the root node of one tree a child of the root node of another tree.
A more detailed explanation is available here: TODO
State of compression
State compression is a programming trick. It is mainly applicable to the situation where there are few types of basic states, and sometimes multiple states need to be combined. We’ll call the process of encoding the state into an integer state compression.
For example, there are seven basic states of a single cell (more on those later), and a row can have at most eight cells, so there are 787^878 states in a row. Therefore, the status of a row can be expressed as a uint32(unsigned 32-bit integer). The expression is as follows:
Add a row of MMM cells numbered 000 to m−1m-1m−1. The state of the ith lattice is Si, SI ∈[0,7]s_i, S_I ∈[0,7] Si, and SI ∈[0,7], which can be represented by three bits.
The 32 bits of a uint32 are numbered from 000 to 313131 in ascending order.
Through an operation can be sis_isi in 32-3 ∗ (m – I) 32-3 * (m – I) – 3 ∗ (m – I), 33-3 ∗ (m – I) 33-3 * (m – I) 33-3 ∗ (m – I), 34−3∗(m− I)34−3 *(M-I)34−3∗(M − I) Three bits.
Now that we have the necessary knowledge, let’s get down to business. Of course, if you want to understand the following parts, you may need to brush through the template questions to deepen your understanding (too ruthless).
Plug DP
! [] (img – blog. Csdnimg. Cn/img_convert… =200×200)
Most of the following conclusions are based on the case scenario. Other topics need to be analyzed on a case-by-case basis.
What is a plug
For a 4-connected problem, there are usually 4 plugs, up, down, left and right. The presence of a plug in one direction means that the grid can be connected to the outside on this side.
The property of the Hamiltonian path determines that all non-obstacle cells except the starting point and ending point must come in one direction and go out the other. That is, 4 plugs have exactly 2 plugs exist, a total of 6 cases. The 6 cases are shown below, with the blue part of the figure representing the part of the path in the cell:
Add in the unplugged scenarios of the obstacle grid, and there are seven.
The starting and ending grids are special and can only have one plug, but we’ll talk about how to deal with this difference later.
How many states are there in each row?
If there are m cells in a row, there are 7m7^m7m states in a row. In this case, m=8m =8m =8, 5764801 states need to be enumerated.
It is not difficult to observe that many of these states are incorrect. For example, if the paths of two adjacent cells are not connected, it will not work.
It is not difficult to observe that when the lattice CJC_JCJ has a right plug, cJ + 1C_ {j+1} Cj +1 can only be in one of three, four, or five states. The rest are all wrong.
! [] (img – blog. Csdnimg. Cn/img_convert… =200x)
In other words, the right plug of the left cell and the left plug of the right cell must either exist or not exist. Because it’s the only way to connect.
Similarly, ci+1,jc_{I +1,j}ci+1,j can only be one of one, four, or six when the JJJ grid ci,jc_{I,j}ci,j in row III has a plug.
! [] (img – blog. Csdnimg. Cn/img_convert… =300x)
This means that when the state of the previous row is determined, we know that each cell of the current row can only choose one, four, six or two, three, five.
Considering whether it is an obstacle grid, each grid has at most two valid choices.
To sum up, when the states of the previous row have been determined, the corresponding effective states of the current row are no more than 2m2^m2m. When m=8m =8m =8, the upper limit is 256, and the number of states is several orders of magnitude smaller
Row status records connectivity
! [] (img – blog. Csdnimg. Cn/img_convert… =400x)
Consider the two cases above, and if the row state only records the plug type, then the two cases are the same — all four sixth plugs.
However, after the same plug is added in the fourth row, the left side forms a Hamilton path, but the right side does not.
! [] (img – blog. Csdnimg. Cn/img_convert… =400x)
This obviously does not accord with the principle of no aftereffect of dynamic programming.
The problem is caused by the fact that the row state only records the plug type and does not record the connectivity between cells.
To solve this problem, the row state needs to hold connectivity information.
How are connected components identified
First, the connectivity problem representing n cells needs to be solved.
Usually each cell is marked with a positive number, and cells belonging to the same connected block are marked with the same number. For example, {1,1,2,2} and {2,2,1,1} both indicate that the first and second cells belong to a connected block, and the third and fourth cells belong to a connected block. In order to avoid different representations of the same connection information, the minimum representation is generally used.
A minimum representation is: all obstacle cells are labeled 0, the first non-obstacle cell and all connected cells are labeled 1, and then the first unmarked non-obstacle cell and all connected cells are labeled 2,…… Repeat the process until all the cells are marked.
! [] (img – blog. Csdnimg. Cn/img_convert… =400x)
For example, these two states are labeled {1,1,2,2}, {1,2,2,1} respectively.
Row state upgrade
In the line state before the upgrade, the plug type of each grid in the line is recorded. Think carefully, do you use plug types when deriving the subsequent states of the next row? No, actually, we only used the information whether there was a plug or not.
! [] (img – blog. Csdnimg. Cn/img_convert… =400x)
So, 1,2,3,4,5,6 in the row state can be reduced to:
- 1,3,4 -> 0: no plug is removed
- 2,5,6 -> non-zero value, indicating a plug down.
How many non-zero values should I put in for 2, 5, and 6? Smart old iron should have guessed, fill in the minimum number of connected components!
Now we can use a single uint32 to represent two kinds of information:
- Connectivity of all grids in front of line III: M ∗im* IM ∗ I grids in front of line III comprise several connected components.
- The grid in line III has no lower plug, and if there is a lower plug, the minimum label of the connected component to which it belongs is recorded.
! [] (img – blog. Csdnimg. Cn/img_convert… =100x)
How many row states can be upgraded
Considering that each effectively connected component is actually part of the Hamiltonian path, each component has only two down plugs on row III.
In other words, in the recursive process, there are at most ⌊m2⌋\lfloor \frac{m}{2} \rfloor⌊2m⌋ components. So, I think a less precise upper limit is
A valid row state. Where KKK is the largest even number not exceeding MMM.
Row state transition
There is an input to the NNN row MMM column, denoted as datadatadata. For ease of handling boundaries, row subscripts start at 1 and column subscripts start at 0.
unordered_map<uint32_t.int> dp[9];
Copy the codeThe above container array DPDPDP records the data of the recursive process.
Initially, there is dp0,0=1dp_{0,0} = 1dp0,0=1, which can be understood as a state without a plug before the first line. As shown below:
! [] (img – blog. Csdnimg. Cn/img_convert… =300x)
The general process of recursion is easy to understand, and the pseudocode is as follows:
for i <- 1 to n :
for j in dp[i] :
forK in {from j and data[I] construction of subsequent state} : dp[I][k] += dp[I][J];Copy the codeEnsure that each connected component has a plug in the state represented by KKK.
See the code at the end of this article for details. If you’ve read this far, I think the code is pretty straightforward.
! [] (img – blog. Csdnimg. Cn/img_convert… =100x)
A few details
Each connected component must have two lower plugs
If a Hamilton path starts and ends at row NNN, a straight line drawn at the junction of any two rows will cross the path an even number of times.
! [] (img – blog. Csdnimg. Cn/img_convert… =300x)
The connected component formed by the line part can be regarded as a local Hamiltonian path, so each Hamiltonian path must have two down plugs at the line.
Therefore, in the recursion process, you need to deal with the incorrect number of plugs. For example, in the figure below, the adjacent plugs are matched, but the red component does not remove the plug, forming a local loop.
! [] (img – blog. Csdnimg. Cn/img_convert… =300x)
Address starting/ending differences
As mentioned earlier, there is only one plug for starting and ending points.
In fact, this can be interpreted as having an unused plug at both the start and end. So for an MMM input, the answer is:
dp[n][1<<((m-1)*3)|1]
code
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
typedef unsigned int uint32_t;
using namespace std;
char data[9] [9];
class Hash {
public:
uint32_t& operator[] (uint32_t k) {
uint32_t index = k & 127;
for (inti = head[index]; i ! =- 1; i= node[i].next) {
if (node[i].k == k) {
return node[i].v;
}
}
node[top].k = k;
node[top].v = 0;
node[top].next = head[index];
head[index] = top;
return node[top++].v;
};
void reset(a) {
top = 0;
memset(head, - 1.sizeof(head));
}
struct Node {
uint32_t k;
uint32_t v;
int next;
} node[1000];
int top;
int head[128];
}dp[9];
uint32_t state[65536];
int state_count = 0;
int find(int *fa, int u) {
int t = u;
while(fa[u] ! = u) { u = fa[u]; }while(fa[t] ! = t) {int tmp = fa[t];
fa[t] = u;
t = tmp;
}
return u;
}
void link(int *fa, int u, int v) {
int fu = find(fa, u);
int fv = find(fa, v);
if (fu > fv) {
fa[fu] = fv;
} else{ fa[fv] = fu; }}void generate_state_dfs(char *line, int *pre_id, uint32_t cur, int index, int m) {
int pre_sta = cur&0x7;
bool has_left = (pre_sta == 1 || pre_sta == 2 || pre_sta == 3);
if (index == m) {
if (has_left == false) {
state[state_count++] = cur;
}
return;
}
boolhas_top = (pre_id[index] ! =0);
if (line[index] == The '#') {
if (has_top == 0 && has_left == false) {
generate_state_dfs(line, pre_id, cur<<3, index+1, m);
}
return;
}
if (has_top && has_left) {
generate_state_dfs(line, pre_id, cur<<3 | 4, index+1, m);
return ;
}
if(has_top && ! has_left) {generate_state_dfs(line, pre_id, cur<<3 | 1, index+1, m);
generate_state_dfs(line, pre_id, cur<<3 | 6, index+1, m);
return ;
}
if(! has_top && has_left) {generate_state_dfs(line, pre_id, cur<<3 | 3, index+1, m);
generate_state_dfs(line, pre_id, cur<<3 | 5, index+1, m);
return ;
}
if(! has_top && ! has_left) {generate_state_dfs(line, pre_id, cur<<3 | 2, index+1, m);
return; }}void generate_state(char *line, int *pre_id, int m) {
if (m <= 1) {
return ;
}
state_count = 0;
generate_state_dfs(line, pre_id, 0.0, m);
}
int main(a) {
int n, m;
dp[0].reset(a); dp[0] [0] = 1;
while (scanf("%d %d", &n, &m) ! = EOF && (n || m)) {for (int i=1; i<=n; i++) {scanf("\n");
for (int j=0; j < m; j++) {scanf("%c",&data[i][j]); }}for (int i = 1; i <= n; i++) {
dp[i].reset(a); }int min_id[16];
int pre_id[8];
int fa[16];
int cur_vs[8];
for (int i = 1; i <= n; i++) {
for (int index = 0; index < dp[i- 1].top; index++) {
uint32_t status = dp[i- 1].node[index].k;
uint32_t count = dp[i- 1].node[index].v;
for (int k = m- 1; k >= 0; k--) {
pre_id[k] = (status&0x7);
status >>= 3;
}
generate_state(data[i], pre_id, m);
for (int j = 0; j < state_count; j++) {
int new_fa[8] = {0};
for (int k = 0; k < m; k++) { fa[k] = k; }
for (int k = 0; k < m; k++) {
if (new_fa[pre_id[k]] == 0) {
new_fa[pre_id[k]] = m+k;
}
fa[k+m] = new_fa[pre_id[k]];
}
uint32_t cs = state[j];
for (int k = m- 1; k >= 0; k--, cs >>= 3) {
cur_vs[k] = (cs&0x7);
switch(cs&0x7) {
case 1:
case 6:
link(fa, k, k+m); break;
case 3:
case 5:
link(fa, k, k- 1); break;
case 4:
link(fa, k, k+m);
link(fa, k, k- 1); break; }}memset(min_id, - 1.sizeof(min_id));
int component_cnt = 0;
for (int k = 0; k < m; k++) {
if (data[i][k] == '. ') {
int f = find(fa, k);
if (min_id[f] == - 1) { min_id[f] = ++component_cnt; } min_id[k] = min_id[f]; }}bool connect_flag = true;
for (int k = 0; k < m && connect_flag; k++) {
if(pre_id[k] ! =0 && find(fa, k+m) >= m) {
connect_flag = false; }}if(! connect_flag) {continue;
}
uint32_t next = 0;
cs = state[j];
bool mark[8] = {0};
for (int k = 0; k < m; k++) {
next <<= 3;
switch(cur_vs[k]) {
case 2:
case 5:
case 6:
next |= min_id[k];
if (mark[min_id[k]] == false) {
mark[min_id[k]] = true; component_cnt--; }}}if(component_cnt ! =0) {
continue; } dp[i][next] += count; }}}int index = (1<<(m- 1) *3) | 1;
printf("%d\n", dp[n][index]);
}
return 0;
}
Copy the codeThe relevant data
- Chen Danqi, “Dynamic Programming Problem Based on Connectivity State Compression”
- Pan.baidu.com/s/1bm1lYZ50…
- g8mk