Skip to content

Definition

Some state compression DP problems require us to record connectivity information of states. Such problems are often vividly called Plug DP or Connectivity State Compression DP. For example, counting Hamiltonian paths on grid graphs, finding the number of ways to black-white color a chessboard such that cells of the same color form a connected component, and counting spanning trees of specific graphs, etc. These problems usually require us to encode the connectivity of states and discuss how connectivity changes during state transitions.

Introduction

Domino Tiling and Contour Line DP

To review and learn new things, before starting to learn Plug DP, let's first revisit a classic problem.

Example 「HDU 1400」Mondriaan’s Dream

Problem summary: Tile an \(N\times M\) chessboard with \(1\times 2\) or \(2\times 1\) dominoes. Find the number of ways.

When \(n\) or \(m\) is not too large, such problems can be solved using state compression DP. Divide stages row by row. Let \(dp(i,s)\) denote the number of ways considering the first \(i\) rows, with the state of the \(i\)-th row being \(s\). Here each bit of state \(s\) indicates whether this position is covered by the previous row.

domino

Another way to divide stages is cell-by-cell DP, also called contour line DP. \(dp(i,j,s)\) denotes the number of ways considering up to row \(i\), column \(j\), with the current contour line state being \(s\).

Although in cell-by-cell DP we add one dimension to the state, the transition time complexity reduces to \(O(1)\), so the overall time complexity remains unchanged. Let \(f_0\) denote the current stage's state, \(f_1\) the next stage's state, and \(u = f_0(s)\) the current enumerated function value. Then the state transition equation is as follows:

1
2
3
4
5
6
if (s >> j & 1) {       // If already covered
  f1[s ^ 1 << j] += u;  // Do not place
} else {                // If not covered
  if (j != m - 1 && (!(s >> j + 1 & 1))) f1[s ^ 1 << j + 1] += u;  // Place horizontally
  f1[s ^ 1 << j] += u;                                             // Place vertically
}

Observe that the equations for "do not place" and "place 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
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 11;
long long f[2][1 << N], *f0, *f1;
int n, m;

int main() {
  while (cin >> n >> m && n) {
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << m), 0);
    f1[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        swap(f0, f1);
        fill(f1, f1 + (1 << m), 0);
#define u f0[s]
        for (int s = 0; s < 1 << m; ++s)
          if (u) {
            if (j != m - 1 && (!(s >> j & 3))) f1[s ^ 1 << j + 1] += u;  // Horizontal placement
            f1[s ^ 1 << j] += u;  // Vertical placement or no placement
          }
      }
    }
    cout << f1[0] << endl;
  }
}
Exercise 「SRM 671. Div 1 900」BearDestroys

Problem summary: Given an \(n\times m\) matrix, each cell is E or S. For a matrix, there is a scoring scheme. Scan each cell in row-major order. If the cell was previously occupied by a domino, skip. Otherwise, try to place a domino. If the placement direction is outside the matrix or occupied by another domino, the placement fails; try the other scheme or skip. If it's E, prioritize placing a \(1\times 2\) domino. If it's S, prioritize placing a \(2\times 1\) domino. The score of a matrix is the number of dominoes finally placed. Find the sum of scores over all \(2^{nm}\) matrices.

Terminology

Stage: The order of dynamic programming execution. Results of later stages depend only on results of earlier stages (no aftereffect). Many DP problems can have multiple ways to divide stages. For example, in the knapsack problem, we can usually divide stages by items or by knapsack capacity (which loop enumerates first). In domino tiling problems, we can divide stages by rows, columns, cells, or diagonals.

Contour line: The boundary between decided and undecided states.

contour line

Plug: A plug exists in a certain direction of a cell, indicating that the cell is connected to its neighbor in that direction.

plug

Path Model

Multiple Loops

Example

Example 「HDU 1693」Eat the Trees

Problem summary: Find the number of ways to cover an \(N\times M\) chessboard with several loops. Some positions have obstacles.

Strictly speaking, multiple loops problems do not belong to Plug DP, because we only need to record whether plugs exist, then merge and generate plugs in pairs, similar to the domino tiling problem above.

Note that for a chessboard of width \(m\), the contour line width is \(m+1\), because it includes \(m\) top plugs and \(1\) left plug. Note that after iterating through a row, the rightmost left plug is usually an invalid state. At the same time, we need to add the first left plug of the next row, which requires adjusting the current contour line state, usually by shifting all states 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
#include <iostream>
using namespace std;
constexpr int N = 11;
long long f[2][1 << (N + 1)], *f0, *f1;
int n, m;

int main() {
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    cin >> n >> m;
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << (m + 1)), 0);
    f1[0] = 1;  // Initialization
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        bool bad;
        cin >> bad;
        bad ^= 1;
        swap(f0, f1);
        fill(f1, f1 + (1 << (m + 1)), 0);
        for (int s = 0; s < 1 << (m + 1); ++s)  // Specific DP transition, everything above is initialization
          if (f0[s]) {
            bool lt = s >> j & 1, up = s >> (j + 1) & 1;
            if (bad) {
              if (!lt && !up) f1[s] += f0[s];
            } else {
              f1[s ^ 3 << j] += f0[s];
              if (lt != up) f1[s] += f0[s];
            }
          }
      }
      swap(f0, f1);
      fill(f1, f1 + (1 << (m + 1)), 0);
      for (int s = 0; s < 1 << m; ++s) f1[s << 1] = f0[s];
    }
    cout << "Case " << Case << ": There are " << f1[0]
         << " ways to eat the trees.\n";
  }
}

Exercises

Exercise 「ZOJ 3466」The Hive II

Problem summary: Same as above, but cells become hexagons.

Single Loop

Example

Example 「Andrew Stankevich Contest 16 - Problem F」Pipe Layout

Problem summary: Find the number of ways to cover an \(N\times M\) chessboard with a single loop.

In the state representation above, each time we merge a set of connected plugs, an independent loop is generated. Thus, in this problem, we also need to distinguish connectivity between plugs (it appears!). This requires additional encoding of the state.

State Encoding

Common encoding schemes include bracket representation and minimum representation. Here we focus on the more versatile minimum representation. We use an integer array of length \(m+1\) to record the state of each plug on the contour line. \(0\) means no plug, and we agree that connected plugs are marked with the same number.

Then the following two encodings represent the same state:

  • 0 3 1 0 1 3
  • 0 1 2 0 2 1

We map all identical states to the lexicographically smallest representation. For example, in the above case, 0 1 2 0 2 1 is a minimum representation.

We use array b[] to represent the plug states on the contour line. bb[] represents, during the minimum representation encoding process, the smallest number each number is mapped to. Note that \(0\) means no plug and cannot be mapped to other values.

Code Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= offset;
    s |= bi;
  }
  return s;
}

void decode(int s) {
  REP(i, m + 1) {
    b[i] = s & mask;
    s >>= offset;
  }
}

We note that plugs always appear and disappear in pairs. Thus, states like 0 1 2 0 1 2 are invalid. Valid states form a bracket sequence. In practice, valid states can be very sparse.

Handwritten Hash

In some state compression DP problems, valid states may be sparse (e.g., this problem). To optimize time and space complexity, we can use a hash table to store valid DP states. For C++ users, we can use std::unordered_map, or we can write our own, which allows flexible encapsulation of the state transition function.

Code 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
constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() { REP(i, sz) state[i] <<= offset; }
} H[2], *H0, *H1;

In the above code:

  • MaxSZ represents the upper bound of valid states, which can be estimated or preprocessed to a more accurate value.
  • Prime is a large prime less than MaxSZ.
  • head[] pointers to the head nodes.
  • next[] pointers to subsequent states.
  • state[] node states.
  • key[] node keys, which in this problem are the number of ways.
  • clear() initialization function, similar to handwritten adjacency lists, we only need to initialize the head node pointers.
  • push() state transition function, where d is a global variable (for convenience), representing the increment brought by each state transition. If found, +=; otherwise, create a new node with state s and key d.
  • roll() after iterating through a whole row, roll the contour line.

For complexity analysis of hash tables, and the differences between open hashing and closed hashing, refer to the relevant chapters on hash tables in Introduction to Algorithms.

State Transition

Code 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
REP(ii, H0->sz) {
  decode(H0->state[ii]);                  // Retrieve state and decode
  d = H0->key[ii];                        // Get increment delta
  int lt = b[j], up = b[j + 1];           // Left plug, top plug
  bool dn = i != n - 1, rt = j != m - 1;  // Bottom plug, right plug
  if (lt && up) {                         // If both left and top plugs exist
    if (lt == up) {                       // From the same connected component
      if (i == n - 1 &&
          j == m - 1) {  // Only at the last cell can we merge and close the loop.
        push(j, 0, 0);
      }
    } else {  // Otherwise, must merge these two components because this problem requires loop coverage
      REP(i, m + 1) if (b[i] == lt) b[i] = up;
      push(j, 0, 0);
    }
  } else if (lt || up) {  // If either left or top plug exists
    int t = lt | up;      // Get this plug
    if (dn) {             // If can extend downward
      push(j, t, 0);
    }
    if (rt) {  // If can extend rightward
      push(j, 0, t);
    }
  } else {           // If neither left nor top plug exists
    if (dn && rt) {  // Generate a new pair of plugs
      push(j, m, m);
    }
  }
}
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
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int M = 10;
constexpr int offset = 3, mask = (1 << offset) - 1;
int n, m;
long long ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() {
    for (int i = 0; i < sz; i++) state[i] <<= offset;
  }
} H[2], *H0, *H1;

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= offset;
    s |= bb[b[i]];
  }
  return s;
}

void decode(int s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & mask;
    s >>= offset;
  }
}

void push(int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1->push(encode());
}

int main() {
  cin >> n >> m;
  if (m > n) swap(n, m);
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 1;
  H1->push(0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      swap(H0, H1);
      H1->clear();
      for (int ii = 0; ii < (H0->sz); ii++) {
        decode(H0->state[ii]);
        d = H0->key[ii];
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            if (i == n - 1 && j == m - 1) {
              push(j, 0, 0);
            }
          } else {
            for (int i = 0; i < m + 1; i++)
              if (b[i] == lt) b[i] = up;
            push(j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(j, t, 0);
          }
          if (rt) {
            push(j, 0, t);
          }
        } else {
          if (dn && rt) {
            push(j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  assert(H1->sz <= 1);
  cout << (H1->sz == 1 ? H1->key[0] : 0) << endl;
}

Exercises

Exercise 「Ural 1519」Formula 1

Problem summary: Find the number of ways to cover an \(N\times M\) chessboard with a single loop. Some positions have obstacles.

Exercise 「USACO 5.4.4」Betsy's Tours

Problem summary: An \(N\times N\) square (\(N\le 7\)). Find the total number of paths from the top-left corner to the bottom-left corner passing through every cell. Although it's a single path, because the start and end are fixed, it can be transformed into a single loop problem.

Exercise 「POJ 1739」Tony's Tour

Problem summary: An \(N\times M\) chessboard. Find the total number of paths from the bottom-left corner to the bottom-right corner passing through every cell. Some positions have obstacles.

Exercise 「USACO 6.1.1」Postal Vans

Problem summary: Find the number of ways to cover a \(4\times N\) chessboard with a single directed loop. Requires high precision.

Exercise 「HNOI 2007」Amusement Park

Problem summary: Given an \(n\times m\) grid, each cell has a weight. Find any loop that maximizes the sum of weights passed through.

Exercise 「ProjectEuler 393」Migrating ants

Problem summary: Cover an \(n\times n\) square with multiple loops. Each solution with \(m\) loops contributes \(2^m\) to the answer. Find the sum of contributions over all solutions.

Single Path

Example

Example 「ZOJ 3213」Beautiful Meadow

Problem summary: An \(N\times M\) square (\(N,M\le 8\)), each grid point has a weight. Find a path that maximizes the sum of weights of covered grid points.

This is a standard single path problem. In single path problems, the encoded state may also contain unpaired independent plugs. The state transition function needs to additionally discuss the generation, merging, and disappearance of independent plugs. The generation and disappearance of independent plugs correspond to the ends of the path, so such events will not occur more than twice (once generation and once disappearance, or twice generation and once merge). Otherwise, the final result will definitely have multiple connected components.

We need to additionally record the total number of such events in the state. We can encode this information into the state (note that such extra information does not need to roll with the contour line adjustment), or we can add a dimension outside the hashTable array. In the example program below, we choose the latter.

State Transition

Code 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
53
REP(i, n) {
  REP(j, m) {
    checkMax(ans, A[i][j]);  // Need to handle the case of a single cell separately
    if (!A[i][j]) continue;  // If there is an obstacle, skip. Note that the state array does not need to roll here.
    swap(H0, H1);
    REP(c, 3)
    H1[c].clear();  // c represents the total number of generation and disappearance events, at most 2
    REP(c, 3) REP(ii, H0[c].sz) {
      decode(H0[c].state[ii]);
      d = H0[c].key[ii] + A[i][j];
      int lt = b[j], up = b[j + 1];
      bool dn = A[i + 1][j], rt = A[i][j + 1];
      if (lt && up) {
        if (lt == up) {  // In a single path problem, we cannot merge identical plugs.
          // Cannot deploy here...
        } else {  // Possibly one of the merging plugs is independent, but can be handled with the same code segment
          REP(i, m + 1) if (b[i] == lt) b[i] = up;
          push(c, j, 0, 0);
        }
      } else if (lt || up) {
        int t = lt | up;
        if (dn) {
          push(c, j, t, 0);
        }
        if (rt) {
          push(c, j, 0, t);
        }
        // Case where a plug disappears. If it's an independent plug, it means disappearance.
        // If it's a paired plug, it's equivalent to generating an independent plug.
        // In either case, we need to increment c by 1.
        if (c < 2) {
          push(c + 1, j, 0, 0);
        }
      } else {
        d -= A[i][j];
        H1[c].push(H0[c].state[ii]);
        d += A[i][j];    // Skip plug generation; this problem does not require full coverage
        if (dn && rt) {  // Generate a pair of plugs
          push(c, j, m, m);
        }
        if (c < 2) {  // Generate an independent plug
          if (dn) {
            push(c + 1, j, m, 0);
          }
          if (rt) {
            push(c + 1, j, 0, m);
          }
        }
      }
    }
  }
  REP(c, 3) H1[c].roll();  // End of a row, adjust contour line
}
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
#include <cstring>
#include <iostream>
using namespace std;

template <class T>
bool checkMax(T &a, const T b) {
  return a < b ? a = b, true : false;
}

constexpr int N = 8, M = 8;
constexpr int offset = 3, mask = (1 << offset) - 1;
int A[N + 1][M + 1];
int n, m;
int ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  int key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        checkMax(key[i], d);
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() {
    for (int i = 0; i < sz; i++) state[i] <<= offset;
  }
} H[2][3], *H0, *H1;

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= offset;
    s |= bb[b[i]];
  }
  return s;
}

void decode(int s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & mask;
    s >>= offset;
  }
}

void push(int c, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1[c].push(encode());
}

void init() {
  cin >> n >> m;
  H0 = H[0], H1 = H[1];
  for (int c = 0; c < 3; c++) H1[c].clear();
  d = 0;
  H1[0].push(0);
  memset(A, 0, sizeof(A));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> A[i][j];
}

void solve() {
  ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      checkMax(ans, A[i][j]);  // Need to handle the case of a single cell separately
      if (!A[i][j]) continue;  // If there is an obstacle, skip. Note that the state array does not need to roll here.
      swap(H0, H1);
      for (int c = 0; c < 3; c++)
        H1[c].clear();  // c represents the total number of generation and disappearance events, at most 2 times.
      for (int c = 0; c < 3; c++)
        for (int ii = 0; ii < H0[c].sz; ii++) {
          decode(H0[c].state[ii]);
          d = H0[c].key[ii] + A[i][j];
          int lt = b[j], up = b[j + 1];
          bool dn = A[i + 1][j], rt = A[i][j + 1];
          if (lt && up) {
            if (lt == up) {  // In a single path problem, we cannot merge identical plugs.
              // Cannot deploy here...
            } else {  // It's possible that one of the two plugs involved in the merge is an independent plug, but it can be handled with the same code snippet.
              for (int i = 0; i < m + 1; i++)
                if (b[i] == lt) b[i] = up;
              push(c, j, 0, 0);
            }
          } else if (lt || up) {
            int t = lt | up;
            if (dn) {
              push(c, j, t, 0);
            }
            if (rt) {
              push(c, j, 0, t);
            }
            // Case where a plug disappears. If it's an independent plug, it means disappearance; if it's a plug that appears in pairs, it's equivalent to generating an independent plug.
            // For either type of event, c needs to be incremented by 1.
            if (c < 2) {
              push(c + 1, j, 0, 0);
            }
          } else {
            d -= A[i][j];
            H1[c].push(H0[c].state[ii]);
            d += A[i][j];  // Skip plug generation, this problem does not require full coverage.
            if (dn && rt) {  // Generate a pair of plugs.
              push(c, j, m, m);
            }
            if (c < 2) {  // Generate an independent plug.
              if (dn) {
                push(c + 1, j, m, 0);
              }
              if (rt) {
                push(c + 1, j, 0, m);
              }
            }
          }
        }
    }
    for (int c = 0; c < 3; c++) H1[c].roll();  // End of a row, adjust the contour line.
  }
  for (int ii = 0; ii < H1[2].sz; ii++) checkMax(ans, H1[2].key[ii]);
  cout << ans << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
  }
}

Exercises

Exercise 「BZOJ 2310」ParkII

Problem summary: \(m\times n\) chessboard, each grid point has a weight. Find a path coverage that maximizes the sum of weights of points passed through.

Exercise 「NOI 2010 Day2」Travel Route

Problem summary: \(n\times m\) chessboard, each cell has a 01 weight T[x][y]. Find a path coverage satisfying:

  • The i-th visited cell (x, y) satisfies T[x][y]= L[i]
  • One end of the path is on the boundary of the chessboard.

Find the number of feasible solutions.

Coloring Model

Besides the path model, there is another common model that requires us to color the chessboard, where adjacent nodes of the same color are considered connected. In path problems, we enumerate the direction of the current path during state transition. In coloring problems, we enumerate which color to assign to the current node. In the coloring model, there may be more than two nodes with the same connectivity in the state. But overall, it's still similar. Let's look at a classic example.

Example 「UVa 10572」Black & White

Example 「UVa 10572」Black & White

Problem summary: In an \(N\times M\) chessboard, color the uncolored grid points black or white. Require all black regions and all white regions to be connected. Also, any \(2\times 2\) sub-rectangle cannot have all cells of the same color (e.g., the situation in the figure below is illegal). Find the number of legal colorings and construct one legal coloring.

black_and_white1

State Encoding

First consider state encoding. Without considering connectivity, it's SGU 197. Nice Patterns Strike Back, which can be directly solved with state compression DP. Now we need to incorporate both color and connectivity information in the state. Examine the state of each position on the contour line. Each Offset bits in binary describe one position on the contour line. Since there are only two colors, we use the parity of the lowest bit to represent color, and the remaining bits for connectivity.

Consider the nodes above the first row and to the left of the first column. To avoid special cases, we could introduce a third color to distinguish them. Here we observe that the connectivity information of these boundary states must be 0, so no additional encoding for a third color is needed.

In path problems, our contour line consists of \(m\) top plugs and \(1\) left plug. In this problem, because we also need to check whether the \(2\times 2\) sub-rectangle with the current cell as the bottom-right corner is legal, we need to record the color of the top-left cell. Therefore, the contour line length is still \(m+1\).

This encoding scheme still retains much redundant information (connected regions must have the same color, and the top-left cell only needs color information, not connectivity). But since we already use hash tables and minimum representation, the impact on time complexity is not significant. To reduce programming pressure, we won't refine further.

In the worst case (e.g., first row alternating black and white), each plug's connectivity information is different, so we need \(4\) bits to record connectivity, plus color information. Thus, Offset is \(5\) bits in this problem.

Code 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
constexpr int Offset = 5, Mask = (1 << Offset) - 1;
int c[N + 2];
int b[N + 2], bb[N + 3];

T_state encode() {
  T_state s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= Offset;
    s |= (bi << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  REP(i, m + 1) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

Handwritten Hash

Because we need to construct any one solution, we need to add an array pre[] to the hash table to record an arbitrary predecessor of each state in the previous stage.

Code 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
constexpr int Prime = 9979, MaxSZ = 1 << 20;

template <class T_state, class T_key>
struct hashTable {
  int head[Prime];
  int next[MaxSZ], sz;
  T_state state[MaxSZ];
  T_key key[MaxSZ];
  int pre[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(T_state s, T_key d, T_state u) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d, pre[sz] = u;
    next[sz] = head[x], head[x] = sz++;
  }

  void roll() { REP(ii, sz) state[ii] <<= Offset; }
};

hashTable<T_state, T_key> _H, H[N][N], *H0, *H1;

Solution Construction

With the above information, we can easily construct a solution. First, iterate through the states in the current hash table. If the number of connected components does not exceed \(2\), count it into the number of solutions. If the number of solutions is not \(0\), we use the pre array to construct a solution in reverse order. Note that at the end of each row, because we performed Roll(), the color needs to be taken from c[j+1].

Code 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
void print() {
  T_key z = 0;
  int u;
  REP(i, H1->sz) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    DWN(i, n, 0) {
      B[i][m] = 0;
      DWN(j, m, 0) {
        decode(H[i][j].state[u]);
        int cc = j == m - 1 ? c[j + 1] : c[j];
        B[i][j] = cc ? 'o' : '#';
        u = H[i][j].pre[u];
      }
    }
    REP(i, n) puts(B[i]);
  }
  puts("");
}

State Transition

We denote:

  • cc color of the cell currently being colored
  • lf color of the left cell
  • up color of the top cell
  • lu color of the top-left cell

We use \(-1\) to indicate no color. Next, discuss state transitions. There are three cases: merge, inherit, and generate.

State Transition - Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void trans(int i, int j, int u, int cc) {
  decode(H0->state[u]);
  int lf = j ? c[j - 1] : -1, lu = b[j] ? c[j] : -1,
      up = b[j + 1] ? c[j + 1] : -1;  // No color is also a type of color!
  if (lf == cc && up == cc) {         // Merge
    if (lu == cc) return;             // Case where 2x2 sub-rectangle is all same color
    int lf_b = b[j - 1], up_b = b[j + 1];
    REP(i, m + 1) if (b[i] == up_b) { b[i] = lf_b; }
    b[j] = lf_b;
  } else if (lf == cc || up == cc) {  // Inherit
    if (lf == cc)
      b[j] = b[j - 1];
    else
      b[j] = b[j + 1];
  } else {                                             // Generate
    if (i == n - 1 && j == m - 1 && lu == cc) return;  // Special case
    b[j] = m + 2;
  }
  c[j] = cc;
  if (!ok(i, j, cc)) return;  // Check if generating a closed connected component would cause illegality
  H1->push(encode(), H0->key[u], u);
}

For the last case, note that if a closed connected region has already been generated, we cannot use its color to color other cells; otherwise, that color would appear in two connected components. We seem to need to record this event separately. We can refer to the approach in 「ZOJ 3213」Beautiful Meadow by adding another dimension to record this event. However, leveraging the specifics of this problem, we can also handle it with a special case.

Special Case - Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
bool ok(int i, int j, int cc) {
  if (cc == c[j + 1]) return true;
  int up = b[j + 1];
  if (!up) return true;
  int c1 = 0, c2 = 0;
  REP(i, m + 1) if (i != j + 1) {
    if (b[i] == b[j + 1]) {  // Same connectivity implies same color
      assert(c[i] == c[j + 1]);
    }
    if (c[i] == c[j + 1] && b[i] == b[j + 1]) ++c1;
    if (c[i] == c[j + 1]) ++c2;
  }
  if (!c1) {               // If a new closed connected block would be generated
    if (c2) return false;  // If there are still same colors on the contour line
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

Further discuss the disappearance of connected components. Whenever we color a cell, if no other cell is connected to the cell above it, a closed connected component is formed. This event can only happen in the last two columns of the last row. Otherwise, to avoid \(2\times 2\) monochromatic connected blocks, this color must appear again, except for the following case:

1
2
3
2 2
o#
#o

We handle this case specially, so in this problem, we can lazily avoid recording whether a closed connected block has been generated.

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
172
```cpp
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
using T_state = long long;
using T_key = int;
constexpr int N = 8;
int n, m;
char A[N + 1][N + 1], B[N + 1][N + 1];
constexpr int Offset = 5, Mask = (1 << Offset) - 1;
int c[N + 2];
int b[N + 2], bb[N + 3];

T_state encode() {
  T_state s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= Offset;
    s |= (bb[b[i]] << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

constexpr int Prime = 9979, MaxSZ = 1 << 20;

template <class T_state, class T_key>
struct hashTable {
  int head[Prime];
  int next[MaxSZ], sz;
  T_state state[MaxSZ];
  T_key key[MaxSZ];
  int pre[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(T_state s, T_key d, T_state u) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d, pre[sz] = u;
    next[sz] = head[x], head[x] = sz++;
  }

  void roll() {
    for (int ii = 0; ii < sz; ii++) state[ii] <<= Offset;
  }
};

hashTable<T_state, T_key> _H, H[N][N], *H0, *H1;

bool ok(int i, int j, int cc) {
  if (cc == c[j + 1]) return true;
  int up = b[j + 1];
  if (!up) return true;
  int c1 = 0, c2 = 0;
  for (int i = 0; i < m + 1; i++)
    if (i != j + 1) {
      if (b[i] == b[j + 1]) {  // If connectivity is the same, color must be the same
        assert(c[i] == c[j + 1]);
      }
      if (c[i] == c[j + 1] && b[i] == b[j + 1]) ++c1;
      if (c[i] == c[j + 1]) ++c2;
    }
  if (!c1) {               // If a new closed connected component would be created
    if (c2) return false;  // If there are still same colors on the contour line
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

void trans(int i, int j, int u, int cc) {
  decode(H0->state[u]);
  int lf = j ? c[j - 1] : -1, lu = b[j] ? c[j] : -1,
      up = b[j + 1] ? c[j + 1] : -1;  // No color is also a type of color!
  if (lf == cc && up == cc) {         // Merge
    if (lu == cc) return;             // Case where the 2x2 sub-rectangle is the same
    int lf_b = b[j - 1], up_b = b[j + 1];
    for (int i = 0; i < m + 1; i++)
      if (b[i] == up_b) {
        b[i] = lf_b;
      }
    b[j] = lf_b;
  } else if (lf == cc || up == cc) {  // Inherit
    if (lf == cc)
      b[j] = b[j - 1];
    else
      b[j] = b[j + 1];
  } else {                                             // Create new
    if (i == n - 1 && j == m - 1 && lu == cc) return;  // Special case
    b[j] = m + 2;
  }
  c[j] = cc;
  if (!ok(i, j, cc)) return;  // Check if it becomes invalid due to creating a closed connected component
  H1->push(encode(), H0->key[u], u);
}

void init() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> A[i];
}

void solve() {
  H1 = &_H, H1->clear(), H1->push(0, 1, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      H0 = H1, H1 = &H[i][j], H1->clear();
      for (int u = 0; u < H0->sz; u++) {
        if (A[i][j] == '.' || A[i][j] == '#') trans(i, j, u, 0);
        if (A[i][j] == '.' || A[i][j] == 'o') trans(i, j, u, 1);
      }
    }
    H1->roll();
  }
}

void print() {
  T_key z = 0;
  int u;
  for (int i = 0; i < H1->sz; i++) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    for (int i = n - 1; i >= 0; i--) {
      B[i][m] = 0;
      for (int j = m - 1; j >= 0; j--) {
        decode(H[i][j].state[u]);
        int cc = j == m - 1 ? c[j + 1] : c[j];
        B[i][j] = cc ? 'o' : '#';
        u = H[i][j].pre[u];
      }
    }
    for (int i = 0; i < n; i++) cout << B[i] << '\n';
  }
  cout << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
    print();
  }
}
```

Exercises

Exercise 「Topcoder SRM 312. Div1 Hard」CheapestIsland

Problem summary: Given a chessboard graph, each cell has a weight. Find the connected component with the minimum sum of weights.

Exercise 「JLOI 2009」Mysterious Creature

Problem summary: Given a chessboard graph, each cell has a weight. Find the connected component with the maximum sum of weights.

Exercise 「AtCoder Beginner Contest 211. Problem E」Red Polyomino

Problem summary: Given an \(N\times N\) chessboard, each cell initially black or white. You can choose exactly \(K\) white cells and color them red. How many coloring schemes make the red cells form a connected component?

Graph Theory Model

Example 「NOI 2007 Day2」Spanning Tree Count

Problem summary: Spanning tree counting for a special type of graph where each node is connected to its first \(k\) preceding nodes.

Example 「2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E」Efficient Tree

Problem summary: Given an \(N\times M\) grid graph and edge weights between adjacent four-connected cells. For a spanning tree, each node's score is 1+[has an edge upward]+[has an edge leftward]. The spanning tree's score is the product of all nodes' scores.

Find: the minimum spanning tree's edge weight sum, and the sum of scores of all minimum spanning trees. (\(n\le 800,m\le 7\))

Practical Section

Example

Example 「HDU 4113」Construct the Great Wall

Problem summary: Construct a set of loops on an \(N\times M\) chessboard to separate all x and o.

There is a class of Plug DP problems that require constructing a set of walls on the chessboard to separate certain elements. We can call them wall construction problems. These problems can be viewed as either coloring models or path models.

greatwall

In this problem, if viewed as a coloring model, we not only need to discuss the perimeter of colored regions but also check for illegal situations due to corner touching (Figure 2). Also, unlike 「UVa 10572」Black & White, this problem requires the wall to be a simple polygon. Thus, the following donut shape is illegal in this problem.

1
2
3
4
3 3
ooo
oxo
ooo

Therefore, we use the path model and transform it into a single loop to handle.

We perform DP along the intersections of the chessboard (thus width and height increase by \(1\)). During each transition, we need to ensure all x are outside the loop and o are inside the loop. So we also need to maintain whether the current position is inside the loop. For this information, we can add a dimension, or directly count the parity of the number of down plugs encountered on the contour line up to this position (ray casting method).

Example Code

```cpp

include

include

using namespace std;

define REP(i, n) for (int i = 0; i < n; ++i)

template bool checkMin(T &a, const T b) { return b < a ? a = b, true : false; }

constexpr int N = 10, M = N; constexpr int offset = 3, mask = (1 << offset) - 1; int n, m; int d; constexpr int INF = 0x3f3f3f3f; int b[M + 1], bb[M + 1];

int encode() { int s = 0; memset(bb, -1, sizeof(bb)); int bn = 1; bb[0] = 0; for (int i = m; i >= 0; --i) {

define bi bb[b[i]]

1
2
3
if (!~bi) bi = bn++;
s <<= offset;
s |= bi;

} return s; }

void decode(int s) { REP(i, m + 1) { b[i] = s & mask; s >>= offset; } }

constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable { int head[Prime], next[MaxSZ], sz; int state[MaxSZ]; int key[MaxSZ];

void clear() { sz = 0; memset(head, -1, sizeof(head)); }

void push(int s) { int x = s % Prime; for (int i = head[x]; ~i; i = next[i]) { if (state[i] == s) { checkMin(key[i], d); return; } } state[sz] = s, key[sz] = d; next[sz] = head[x]; head[x] = sz++; }

void roll() { REP(i, sz) state[i] <<= offset; } } H[2], H0, H1;

char A

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用