Skip to content

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.

domino

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
if (s >> j & 1) {       // already covered
  f1[s ^ 1 << j] += u;  // place nothing
} else {                // not covered yet
  if (j != m - 1 && (!(s >> j + 1 & 1))) f1[s ^ 1 << j + 1] += u;  // place horizontally
  f1[s ^ 1 << j] += u;                                             // place vertically
}

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
#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;  // place horizontally
            f1[s ^ 1 << j] += u;  // place vertically or place nothing
          }
      }
    }
    cout << f1[0] << endl;
  }
}
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.

contour line

Plug: a cell has a plug in some direction if it is connected to the adjacent cell in that direction.

plug

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
#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)  // the DP transitions proper; 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";
  }
}

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 3
  • 0 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
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;
  }
}

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
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 code above:

  • MaxSZ is an upper bound on the number of valid states. It can be estimated, or a fairly exact value can be precomputed.
  • Prime is a large prime smaller than MaxSZ.
  • 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. Here d is 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 state s and key d.
  • 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
REP(ii, H0->sz) {
  decode(H0->state[ii]);                  // fetch the state and decode it
  d = H0->key[ii];                        // the increment delta
  int lt = b[j], up = b[j + 1];           // left plug, up plug
  bool dn = i != n - 1, rt = j != m - 1;  // down plug, right plug
  if (lt && up) {                         // both a left plug and an up plug
    if (lt == up) {                       // they belong to the same connected component
      if (i == n - 1 &&
          j == m - 1) {  // they may be merged, closing the cycle, only at the last cell.
        push(j, 0, 0);
      }
    } else {  // otherwise the two components must be merged, because this problem asks for a cycle cover
      REP(i, m + 1) if (b[i] == lt) b[i] = up;
      push(j, 0, 0);
    }
  } else if (lt || up) {  // exactly one of the left plug and the up plug
    int t = lt | up;      // take that plug
    if (dn) {             // if it can extend downward
      push(j, t, 0);
    }
    if (rt) {  // if it can extend to the right
      push(j, 0, t);
    }
  } else {           // neither a left plug nor an up plug
    if (dn && rt) {  // create 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;
}

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
REP(i, n) {
  REP(j, m) {
    checkMax(ans, A[i][j]);  // a path of a single cell must be handled separately
    if (!A[i][j]) continue;  // skip obstacles; note that the state array is not rolled here
    swap(H0, H1);
    REP(c, 3)
    H1[c].clear();  // c is the total number of creation 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 the single path problem, two plugs with the same label cannot be merged.
          // Cannot deploy here...
        } else {  // one of the two plugs being merged may be a lone plug, but the same code handles that
          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);
        }
        // The plug ends here: a lone plug disappears, while a paired plug leaves its partner as a new lone plug.
        // Either event increases 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];    // create no plug: this problem does not require covering every cell
        if (dn && rt) {  // create a pair of plugs
          push(c, j, m, m);
        }
        if (c < 2) {  // create a lone 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 the row: adjust the profile
}
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]);  // a path of a single cell must be handled separately
      if (!A[i][j]) continue;  // skip obstacles; note that the state array is not rolled here
      swap(H0, H1);
      for (int c = 0; c < 3; c++)
        H1[c].clear();  // c is the total number of creation and disappearance events, at most 2
      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 the single path problem, two plugs with the same label cannot be merged.
              // Cannot deploy here...
            } else {  // one of the two plugs being merged may be a lone plug, but the same code handles that
              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);
            }
            // The plug ends here: a lone plug disappears, while a paired plug leaves its partner as a new lone plug.
            // Either event increases 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];  // create no plug: this problem does not require covering every cell
            if (dn && rt) {  // create a pair of plugs
              push(c, j, m, m);
            }
            if (c < 2) {  // create a lone 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 the row: adjust the profile
  }
  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();
  }
}

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.

black_and_white1

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
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;
  }
}

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
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;

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
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 transitions

Let:

  • cc be the color of the cell being colored
  • lf be the color of the cell to the left
  • up be the color of the cell above
  • lu be 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
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 a color too!
  if (lf == cc && up == cc) {         // merge
    if (lu == cc) return;             // the 2x2 subrectangle would be one 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 {                                             // create
    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 whether closing off a connected component makes the state invalid
  H1->push(encode(), H0->key[u], u);
}

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
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 label 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 this would close off a connected component
    if (c2) return false;  // if the same color still appears on the profile
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

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
2 2
o#
#o

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
#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]) {  // same connectivity label 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 this would close off a connected component
    if (c2) return false;  // if the same color still appears on the profile
    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 a color too!
  if (lf == cc && up == cc) {         // merge
    if (lu == cc) return;             // the 2x2 subrectangle would be one color
    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
    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 whether closing off a connected component makes the state invalid
  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();
  }
}

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.

greatwall

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
3 3
ooo
oxo
ooo

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
#include <cstring>
#include <iostream>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; ++i)

template <class T>
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]]
    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[N + 1][M + 1];

void push(int i, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  if (A[i][j] != '.') {
    bool bad = A[i][j] == 'o';
    REP(jj, j + 1) if (b[jj]) bad ^= 1;
    if (bad) return;
  }
  H1->push(encode());
}

int solve() {
  cin >> n >> m;
  int ti, tj;
  REP(i, n) {
    scanf("%s", A[i]);
    REP(j, m) if (A[i][j] == 'o') ti = i, tj = j;
    A[i][m] = '.';
  }
  REP(j, m + 1) A[n][j] = '.';
  ++n, ++m, ++ti, ++tj;
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 0;
  H1->push(0);
  int z = INF;
  REP(i, n) {
    REP(j, m) {
      swap(H0, H1);
      H1->clear();
      REP(ii, H0->sz) {
        decode(H0->state[ii]);
        d = H0->key[ii] + 1;
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            int cnt = 0;
            REP(i, m + 1) if (b[i])++ cnt;
            if (cnt == 2 && i == ti && j == tj) {
              checkMin(z, d);
            }
          } else {
            REP(i, m + 1) if (b[i] == lt) b[i] = up;
            push(i, j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(i, j, t, 0);
          }
          if (rt) {
            push(i, j, 0, t);
          }
        } else {
          --d;
          push(i, j, 0, 0);
          ++d;
          if (dn && rt) {
            push(i, j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  if (z == INF) z = -1;
  return z;
}

int main() {
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    printf("Case #%d: %d\n", Case, solve());
  }
}

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.

4796

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:

  1. It starts at the top-left corner and ends at the bottom-right corner.
  2. It does not pass through rock.
  3. 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.

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.

domino_v2_transform_matrix

When \(n,m\le 100\), the FKT algorithm can be used to count the perfect matchings of the corresponding planar graph.

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.