Plug DP
Definition
Some bitmask DP problems require the state to record connectivity information. Such problems are usually called plug DP, or connectivity-profile DP. Examples include counting Hamiltonian paths in a grid graph, counting the black-and-white colorings of a board in which each color forms a single connected component, and counting the spanning trees of certain graphs. They usually require us to encode the connectivity of the state and to work out how it changes in each transition.
Introduction
Domino tiling and broken-profile DP
Reviewing the old is a good way to learn the new, so before starting on plug DP let us revisit a classic problem.
Example: [HDU 1400] Mondriaan’s Dream
Problem statement: count the ways to tile an \(N\times M\) board completely with \(1\times 2\) and \(2\times 1\) dominoes.
When \(n\) or \(m\) is small, problems of this kind can be solved with bitmask DP. Take the rows as stages, and let \(dp(i,s)\) be the number of ways in which the first \(i\) rows have been processed and row \(i\) is in state \(s\). Each bit of \(s\) can record whether that position is already covered from the previous row.
The stages can also be the individual cells. This is cell-by-cell DP, also known as broken-profile DP. Here \(dp(i,j,s)\) is the number of ways in which we have reached row \(i\), column \(j\), and the state on the current profile is \(s\).
Cell-by-cell DP adds a dimension to the state, but a transition now takes only \(O(1)\) time, so the time complexity is unchanged. Let \(f_0\) hold the states of the current stage and \(f_1\) those of the next stage, and let \(u = f_0(s)\) be the value currently being enumerated. The recurrence is then:
1 2 3 4 5 6 | |
The transitions for placing nothing and for placing vertically can be merged.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | |
Practice problem: [SRM 671. Div 1 900] BearDestroys
Problem statement: given an \(n\times m\) matrix in which every cell contains E or S.
A matrix is scored as follows. Scan the cells in row-major order. If a cell is already occupied by a domino, skip it.
Otherwise try to place a domino. If the domino would stick out of the matrix or overlap another domino, the placement fails: try the other orientation, or skip the cell.
On an E, try a \(1\times 2\) domino first;
on an S, try a \(2\times 1\) domino first.
The score of a matrix is the number of dominoes placed in the end.
Find the sum of the scores of all \(2^{nm}\) matrices.
Terminology
Stage: the order in which the dynamic programming is carried out. The results of later stages depend only on the results of earlier ones (the no-aftereffect property). Many DP problems can be divided into stages in more than one way. In the knapsack problem, for example, the stages can usually be either the items or the knapsack capacities (whichever the outer loop enumerates). In the domino problem, the stages can be rows, columns, cells, diagonals and so on.
Profile: the boundary between the decided states and the undecided ones.
Plug: a cell has a plug in some direction if it is connected to the adjacent cell in that direction.
Path models
Multiple cycles
Example
Example: [HDU 1693] Eat the Trees
Problem statement: count the ways to cover an \(N\times M\) board with any number of cycles; some cells are obstacles.
Strictly speaking, the multiple-cycles problem is not plug DP: as in the domino tiling problem above, it is enough to record whether each plug exists, and then to merge and create plugs in pairs.
For a board of width \(m\) the profile has width \(m+1\), because it holds \(m\) up plugs and \(1\) left plug. When a row has been processed, a left plug in the rightmost position is usually an invalid state, and the first left plug of the next row has to be added. The states on the current profile must therefore be adjusted, usually by shifting every state left. We call this operation rolling, roll().
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | |
Practice problems
Practice problem: [ZOJ 3466] The Hive II
Problem statement: the same as the previous problem, but the cells are hexagons.
A single cycle
Example
Example: [Andrew Stankevich Contest 16 - Problem F] Pipe Layout
Problem statement: count the ways to cover an \(N\times M\) board with a single cycle.
With the state representation above, every time we merge a pair of connected plugs we close off a separate cycle. In this problem we therefore also have to tell which plugs are connected to which (and there it is!). This takes extra encoding in the state.
State encoding
The usual encodings are the bracket representation and the minimal representation. We concentrate on the minimal representation, which applies more widely. An integer array of length \(m+1\) records the state of each plug on the profile: \(0\) means that there is no plug, and connected plugs are marked with the same number.
The following two encodings then represent the same state:
0 3 1 0 1 30 1 2 0 2 1
We map all encodings of the same state to the lexicographically smallest one. In the example above, 0 1 2 0 2 1 is a minimal representation.
The array b[] holds the states of the plugs on the profile. While the minimal representation is being computed, bb[] holds the smallest number that each number is mapped to. Note that \(0\) means that the plug does not exist, so it cannot be mapped to any other value.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
Plugs always appear in pairs and disappear in pairs, so a state such as 0 1 2 0 1 2 is invalid. The valid states form bracket sequences, and in practice they can be very sparse.
Hand-written hash table
In some bitmask DP problems, this one included, the valid states are sparse. To save time and memory, we can store the valid DP states in a hash table. C++ contestants can use std::unordered_map, or write the table by hand, which gives the flexibility to wrap the transition function into it as well.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
In the code above:
MaxSZis an upper bound on the number of valid states. It can be estimated, or a fairly exact value can be precomputed.Primeis a large prime smaller thanMaxSZ.head[]holds the pointers to the head nodes of the lists.next[]holds the pointers to the next state.state[]holds the state of each node.key[]holds the key of each node, which in this problem is the number of ways.clear()initializes the table. As with a hand-written adjacency list, only the head pointers need to be initialized.push()is the transition function. Heredis a global variable (out of laziness) that holds the increment brought by each transition. If the state is found, we do+=; otherwise we create a new node with statesand keyd.roll()rolls the profile after a whole row has been processed.
For the complexity analysis of hash tables and the difference between open hashing and closed hashing, see the chapters on hash tables in Introduction to Algorithms.
State transitions
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | |
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | |
Practice problems
Practice problem: [Ural 1519] Formula 1
Problem statement: count the ways to cover an \(N\times M\) board with a single cycle; some cells are obstacles.
Practice problem: [USACO 5.4.4] Betsy's Tours
Problem statement: on an \(N\times N\) square board (\(N\le 7\)), count the paths that start at the top-left corner, end at the bottom-left corner and visit every cell. This asks for a path, but because both endpoints are fixed it can be turned into a single-cycle problem.
Practice problem: [POJ 1739] Tony's Tour
Problem statement: on an \(N\times M\) board, count the paths that start at the bottom-left corner, end at the bottom-right corner and visit every cell; some cells are obstacles.
Practice problem: [USACO 6.1.1] Postal Vans
Problem statement: count the ways to cover a \(4\times N\) board with a single directed cycle; arbitrary precision is required.
Practice problem: [HNOI 2007] Magical Amusement Park
Problem statement: given an \(n\times m\) grid graph with a weight in every cell, find any cycle that maximizes the sum of the weights it passes through.
Practice problem: [ProjectEuler 393] Migrating ants
Problem statement: cover an \(n\times n\) square board with several cycles. A cover with \(m\) cycles contributes \(2^m\) to the answer. Find the sum of the contributions of all covers.
A single path
Example
Example: [ZOJ 3213] Beautiful Meadow
Problem statement: in an \(N\times M\) grid (\(N,M\le 8\)) every cell has a weight. Find a path that maximizes the sum of the weights of the cells it covers.
This is the standard single-path problem. In a single-path problem the encoded state can also contain lone plugs, which have no partner. The transition function must additionally handle the creation, merging and disappearance of lone plugs. A lone plug is created or disappears at an end of the path, so such events cannot happen more than twice (one creation and one disappearance, or two creations and one merge); otherwise the final result would have more than one connected component.
The state must additionally record how many such events have happened so far. This count can be encoded into the state itself (note that extra information of this kind must not be rolled along when the profile is adjusted), or added as an extra dimension outside the hashTable array. The sample program below does the latter.
State transitions
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | |
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | |
Practice problems
Practice problem: [BZOJ 2310] ParkII
Problem statement: on an \(m\times n\) board every cell has a weight. Find a path that maximizes the sum of the weights of the cells it passes through.
Practice problem: [NOI 2010 Day2] Travel Route
Problem statement: on an \(n\times m\) board every cell has a 0/1 weight T[x][y]. We look for a path that covers the board such that:
- the i-th cell visited, (x, y), satisfies T[x][y]= L[i]
- one end of the path lies on the border of the board
Count the valid paths.
Coloring models
Besides path models there is another common family of models, in which the board is to be colored and adjacent nodes of the same color count as connected. In path problems a transition enumerates the direction the current path takes; in coloring problems it enumerates the color of the current node. In a coloring model, more than two nodes of a state may share the same connectivity label. On the whole, though, the two are much alike. Let us look at a classic example.
Example: [UVa 10572] Black & White
Example: [UVa 10572] Black & White
Problem statement: color the uncolored cells of an \(N\times M\) board black or white so that the black region is connected, the white region is connected, and no \(2\times 2\) subrectangle is of a single color (the situation in the figure below, for example, is invalid). Count the valid colorings and construct one of them.
State encoding
Consider the state encoding first. Without connectivity, this is SGU 197. Nice Patterns Strike Back, which is easy to solve directly with bitmask DP. Now the state has to carry both color and connectivity information. Look at the state of each position on the profile: every Offset bits of the binary state describe one position. There are only two colors, black and white, so the parity of the lowest bit gives the color and the remaining bits give the connectivity.
Consider the nodes above the first row and those to the left of the first column. To avoid special-casing them, we could introduce a third color to tell them apart. But the connectivity information of these boundary states is always 0, so the third color needs no extra encoding.
In path problems the profile consists of \(m\) up plugs and \(1\) left plug. In this problem we also have to check whether the \(2\times 2\) subrectangle whose bottom-right corner is the current cell is valid, so the color of the top-left cell must be recorded. The profile therefore still has length \(m+1\).
This encoding still keeps a lot of redundant information (connected regions always have the same color, and the top-left cell needs only its color, not its connectivity). But since a hash table and the minimal representation are already in use, the effect on the time complexity is small, and to keep the coding effort down we do not refine it further.
In the worst case (for example, a first row that alternates between black and white) every plug has different connectivity information, so we need \(4\) bits to record connectivity. Together with the color, Offset is \(5\) bits in this problem.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | |
Hand-written hash table
Because we have to construct one solution, the hash table here gets an extra field pre[], which records for each state any one of its predecessors in the previous stage.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | |
Constructing a solution
With this information a solution is easy to construct. First traverse the states in the current hash table, and add each state with at most \(2\) connected components to the count. If the number of ways is not \(0\), walk backward through the pre array to build a solution. Note that at the end of each row the color must be taken from c[j+1], because we have executed Roll() there.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
State transitions
Let:
ccbe the color of the cell being coloredlfbe the color of the cell to the leftupbe the color of the cell abovelube the color of the cell above and to the left
We use \(-1\) for a color that does not exist. Now for the transitions. There are three cases: merge, inherit and create.
State transitions - code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
In the last case, note that once a closed connected region has been formed, its color must not be used again, or that color would end up with two connected components. It seems that we need to record this event as well; as in [ZOJ 3213] Beautiful Meadow, we could add a dimension for it. But this problem is special enough that we can special-case it instead.
Special-casing - code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
Now look more closely at how a connected component disappears. Whenever a cell has been colored and no other cell is connected to the cell above it, a closed connected component is formed. This can happen only in the last two columns of the last row. Anywhere else the color would have to appear again later, to avoid a single-colored \(2\times 2\) block, except in the following case:
1 2 3 | |
We special-case this situation. In this problem we can then be lazy and not record whether a closed connected component has already been formed.
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | |
Practice problems
Practice problem: [Topcoder SRM 312. Div1 Hard] CheapestIsland
Problem statement: given a board with a weight in every cell, find the connected component with the smallest total weight.
Practice problem: [JLOI 2009] Mysterious Creatures
Problem statement: given a board with a weight in every cell, find the connected component with the largest total weight.
Practice problem: [AtCoder Beginner Contest 211. Problem E] Red Polyomino
Problem statement: given an \(N\times N\) board in which every cell is initially black or white, choose exactly \(K\) of the white cells and paint them red. Count the colorings in which the red cells form a single connected component.
Graph models
Example: [NOI 2007 Day2] Counting Spanning Trees
Problem statement: count the spanning trees of a special kind of graph, in which every node is joined by an edge to exactly the \(k\) nodes before it.
Example: [2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E] Efficient Tree
Problem statement: given an \(N\times M\) grid graph and the edge weights between 4-adjacent cells. In a spanning tree, the score of a node is 1+[it has an edge going up]+[it has an edge going left]. The score of a spanning tree is the product of the scores of its nodes.
Find the total edge weight of a minimum spanning tree, and the sum of the scores of all minimum spanning trees. (\(n\le 800,m\le 7\))
In practice
Example
Example: [HDU 4113] Construct the Great Wall
Problem statement: on an \(N\times M\) board, construct a set of cycles that separates all the x from all the o.
One class of plug DP problems asks us to build walls on the board that separate certain elements of the board from others. Let us call them wall-building problems. They can be treated either as a coloring model or as a path model.
Treated as a coloring model, this problem would require us to track the perimeter of the colored regions, and also to detect the invalid case in which regions touch at a corner (Figure 2). Moreover, unlike [UVa 10572] Black & White, this problem requires the wall to be a simple polygon, so the ring-shaped case below is invalid here.
1 2 3 4 | |
So we use the path model and reduce the problem to a single cycle.
We run the DP over the intersection points of the board (so its length and width grow by \(1\)). Every transition must keep all the x outside the cycle and all the o inside it, so we also need to know whether the current position is inside the cycle. We can add a dimension for this, or simply take the parity of the number of down plugs that occur on the profile before this position (ray casting).
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | |
Practice problems
Practice problem: [SCOI 2011] Floor
Problem statement: some cells of an \(r\times c\) board are obstacles. Count the ways to tile all the other cells with L-shaped tiles.
Practice problem: [HDU 4796] Winter's Coming
Problem statement: color the uncolored cells of an \(N\times M\) board black, white or gray so that the black region is connected, the white region is connected, the black and white regions are connected to the top and bottom borders of the board respectively, and no black cell is adjacent to a white cell. Every cell has a cost. Find a coloring that minimizes the cost of the gray region.

Practice problem: [ZOJ 2125] Rocket Mania
Problem statement: every cell of a \(9\times6\) map holds a pipe (shaped like -, T, L or +, or no pipe at all), and pipes can be rotated by 0°, 90°, 180° or 270°. Find the maximum number of rows whose right border can be connected through pipes to the left border of row X.
Practice problem: [ZOJ 2126] Rocket Mania Plus
Problem statement: every cell of a \(9\times6\) map holds a pipe (shaped like -, T, L or +, or no pipe at all), and pipes can be rotated by 0°, 90°, 180° or 270°. Find the maximum number of rows whose right border can be connected through pipes to the left border.
Practice problem: [World Finals 2009/2010 Harbin] Channel
Problem statement: on a grid map, . is open ground and # is rock. Find the longest path such that:
- It starts at the top-left corner and ends at the bottom-right corner.
- It does not pass through rock.
- It does not close up on itself in the 8-connected sense (that is, it may not touch itself even at a corner).
Practice problem: [HDU 3958] Tower Defence
Problem statement: the problem reduces to finding a longest path from \(\mathit{S}\) to \(\mathit{T}\) that does not touch itself; touching at corners is allowed.
Practice problem: [UVa 10531] Maze Statistics
Problem statement: in an \(N\times M\) grid, every cell independently becomes an obstacle with probability \(\mathit{p}\). You want to walk from the top-left corner of the maze to the bottom-right corner. For every cell, find the probability that it is an obstacle in a solvable maze (one whose start and end are 4-connected). (\(N \le 5\), \(M \le 6\))
Practice problem: [Aizu 2452] Pipeline Plans
Problem statement: there are 12 kinds of patterned tiles, with a given number of each. They are to be laid on a rectangular floor, viewed as an \(R\times C\) grid graph, one tile per cell, so that the center of the top-left cell is connected to the center of the bottom-right cell through the lines drawn on the tiles. \((2 \le R \times C \le 15)\)
Practice problem: [SDOI 2014] Circuit Board
Problem statement: on an \(N\times M\) circuit board, some cells are obstacles that wires cannot pass through. Given \(K\) pairs of cells, connect each pair by a wire so that no two wires cross (one wire may enter a cell through its top side and leave through its left side while another enters the same cell through its bottom side and leaves through its right side). Treating wires as undirected edges, find the minimum total wire length that meets the requirements and the number of ways to achieve it.
Practice problem: [SPOJ CAKE3] Delicious Cake
Problem statement: a cake, viewed as an \(N\times M\) grid, is cut along the grid lines into several pieces. Count the different ways to cut it. Two ways are the same if and only if every piece has the same shape and the same position in both. (\(\min(N,M) \le 5, \max(N,M) \le 130\))
Notes
Plug DP problems are usually hard to code and involve intricate case analysis, so they belong to one of the more obscure corners of OI/ACM. The classic reference is the 2008 Chinese national training team paper by Danqi Chen, Dynamic Programming Problems Based on Connectivity State Compression (in Chinese). Next, in 2011 notonlysuccess of HDU wrote two consecutive blog posts on the topic that work up from the basics. They are rare good material too, though nowadays you have to dig them out of the Web Archive.
- notonlysuccess, [Collection] Plug DP (in Chinese)
- notonlysuccess, [Complete Edition] Plug DP (in Chinese)
Domino tiling
[HDU 1400] Mondriaan’s Dream also appears in Beginning Algorithm Contests: Training Guide, as the example of the section "Dynamic Programming on a Profile". Domino tiling is a family of classic mathematical problems: small changes to the constraints give subproblems of different difficulty that call for different algorithms.
With \(m=2\) fixed, domino tiling is equivalent to the Fibonacci sequence. Concrete Mathematics uses this problem to introduce the Fibonacci sequence, and obtains its closed-form solution in several ways.
When \(m\le 10,n\le 10^9\), the recurrence can be precomputed in matrix form and sped up with matrix multiplication.
When \(n,m\le 100\), the FKT algorithm can be used to count the perfect matchings of the corresponding planar graph.
- [51nod 1031] Domino Tiling
- [51nod 1033] Domino Tiling V2|[Vijos 1194] Domino
- [51nod 1034] Domino Tiling V3|[Ural 1594] Aztec Treasure
- Wolfram MathWorld, Chebyshev Polynomial of the Second Kind
A single path
The single-path problem is a special case of the Hamiltonian path problem on grid graphs. The decision version of the Hamiltonian path problem is an important member of the NP-complete family.
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, lychees, 24OI-bot, sshwy, Chrogeek, diauweb, Enter-tainer, isdanni, StudyingFather, thredreams, Early0v0, Xeonacid, mcendu, kenlig, ksyx, Alphnia, Marcythm, StarryReverie, NachtgeistW, ouuan, CCXXXI, shuzhouliu, iamtwz, ImpleLee, billchenchina, Tiphereth-A, zhu-yifang, gi-b716, Molmin, HeRaNO, c-forrest, lailai0916, sun2snow (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.