NeFut Logo NeFut
中 Admin Login

Plug Dynamic Programming: The Ultimate Algorithm for Solving Connectivity Path Loops on Grids

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #Dynamic Programming #DP

Core Logic and Mathematical Principles

Plug Dynamic Programming (Plug DP), also known as Profile Dynamic Programming, is the most dominant and ultimate form of state compression dynamic programming. It is specifically designed to solve the connectivity path loop problem on grids (for example, drawing a non-self-intersecting closed loop on the grid, or counting the number of Hamiltonian cycles).

In Section 17.2's grid compression, we performed inter-row transfers on a "whole row" basis. However, if the constraint changes to "the path must be connected and non-self-intersecting," merely recording the state of the previous row cannot reveal how the current segments are connected on a macro level. Blindly recording the connectivity network of the entire graph will lead to an exponential collapse of the state quantity.

Plug DP introduces Profiles and Plugs, perfectly transforming the global connectivity constraints into precise recursions of local dynamic programming.

1. Geometric Dimensionality Reduction: From "Row Transfer" to "Cell-by-Cell Profile Transfer"

Plug DP no longer advances row by row but cell by cell (Cell by Cell).

2. Algebraic Decoupling of Connectivity: Bracket Notation

Knowing only the positions of plugs on the profile (binary compression) is insufficient, as we cannot determine which two plugs are internally connected. If we accidentally close two paths that originally belong to the same connected component too early, it will create a "locally independent small loop" in the middle of the graph, leading to a failure in determining the global Hamiltonian cycle.

Since the paths do not intersect in the planar grid, the connectivity relationships of the plugs on the profile have a natural nesting property, which is mathematically isomorphic to ground state bracket matching:

This state compression based on three states (0, 1, 2) is usually mapped in memory using base-4 (Bitwise Base-4). A grid with $M$ columns has $M+1$ positions on the profile, and the state scalar is represented using bitwise operations as: State = (p_0 p_1 ... p_{M})_4.

State Design and Algorithm Derivation (Taking Hamiltonian Cycle as an Example)

As we roll from left to right and top to bottom to decide on the grid point $(i, j)$, the states of the left profile plug $L$ and upper profile plug $U$ are known. We need to classify the discussion of their bracket forms to determine the dynamic transfer mechanism for the new plugs on the right and below (classification discussion matrix):

1. Case A: $L = 0, U = 0$ (No plugs flowing in)

Since this is a Hamiltonian cycle, every cell must be traversed by the path. To survive, the current cell must create a new path extending right and down from nothing.

2. Case B: One of $L$ and $U$ is 0, the other is not

This indicates that a path is flowing in from one side, giving the current cell two choices: either continue straight or turn.

3. Case C: $L = 1, U = 1$ (Two left brackets collide)

Two left endpoints of different connected components converge at the current cell. After connecting, these two paths globally form one.

4. Case D: $L = 2, U = 2$ (Two right brackets collide)

Symmetrically to Case C, two right brackets connect.

5. Case E: $L = 2, U = 1$ (Right bracket collides with left bracket)

This indicates that two different path segments perfectly connect in the middle.

6. Case F: $L = 1, U = 2$ (Left bracket collides with right bracket)

This is the most critical endgame determination! The left bracket is on the left and the right bracket is on the right, indicating that they are the two endpoints of the same connected component. If they connect, it will completely close the connected component into a loop.

C++ Standard Source Code (NOIP/Provincial Selection High Precision Constant General Template)

Due to the extremely sparse valid states of Plug DP (although the upper limit is $4^{M+1}$, the legal states that satisfy bracket matching are extremely few), during the exam, it is essential to use a hash table to dynamically maintain and roll forward the state space.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int HASH_SIZE = 4001; // Hash table capacity
const int MAX_STATES = 100005;

int n, m;
int maze[15][15];
int end_x, end_y; // Record the position of the last empty cell

struct HashTable {
    int head[HASH_SIZE], next[MAX_STATES], size;
    long long state[MAX_STATES], value[MAX_STATES];

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

    void insert(long long st, long long val) {
        int key = st % HASH_SIZE;
        for (int i = head[key]; i != -1; i = next[i]) {
            if (state[i] == st) {
                value[i] += val; // State already exists, accumulate the number of schemes
                return;
            }
        }
        // Insert new state
        state[size] = st;
        value[size] = val;
        next[size] = head[key];
        head[key] = size++;
    }
} ht[2]; // Rolling hash table

// Helper Operator: Get the bracket state of the i-th position in base-4 state
inline int get_bit(long long st, int i) {
    return (st >> (i << 1)) & 3;
}

// Helper Operator: Set the bracket state of the i-th position in base-4 state
inline long long set_bit(long long st, int i, int v) {
    return (st & ~(3LL << (i << 1))) | ((long long)v << (i << 1));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m)) return 0;

    end_x = 0; end_y = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char ch; cin >> ch;
            if (ch == '.') {
                maze[i][j] = 1;
                end_x = i; end_y = j; // Dynamically locate the endpoint
            }
        }
    }

    long long ans = 0;
    int cur = 0;
    ht[cur].clear();
    ht[cur].insert(0, 1); // Initial no plugs, number of schemes is 1

    for (int i = 1; i <= n; ++i) {
        // Critical exam detail: When switching lines, the profile must shift right by one cell
        // In base-4, this is equivalent to shifting all states left by 2 bits (i.e., adding a no plug state 0 on the leftmost side)
        for (int k = 0; k < ht[cur].size; ++k) {
            ht[cur].state[k] <<= 2;
        }

        for (int j = 1; j <= m; ++j) {
            int nxt = cur ^ 1;
            ht[nxt].clear();

            for (int k = 0; k < ht[cur].size; ++k) {
                long long st = ht[cur].state[k];
                long long val = ht[cur].value[k];

                int p_left = get_bit(st, j - 1); // Left plug L
                int p_up = get_bit(st, j);       // Upper plug U

                if (!maze[i][j]) {
                    // If it is an obstacle cell, no plugs can flow in or out
                    if (p_left == 0 && p_up == 0) {
                        ht[nxt].insert(st, val);
                    }
                    continue;
                }

                // Classify discussion of state machine matrix
                if (p_left == 0 && p_up == 0) {
                    // Case A: Add a new pair of brackets
                    if (maze[i][j + 1] && maze[i + 1][j]) {
                        long long new_st = set_bit(st, j - 1, 1);
                        new_st = set_bit(new_st, j, 2);
                        ht[nxt].insert(new_st, val);
                    }
                }
                else if (p_left == 0 || p_up == 0) {
                    // Case B: Single plug continuation
                    int p_val = p_left ? p_left : p_up;
                    if (maze[i][j + 1]) { // Extend right
                        long long new_st = set_bit(st, j - 1, 0);
                        new_st = set_bit(new_st, j, p_val);
                        ht[nxt].insert(new_st, val);
                    }
                    if (maze[i + 1][j]) { // Extend down
                        long long new_st = set_bit(st, j - 1, p_val);
                        new_st = set_bit(new_st, j, 0);
                        ht[nxt].insert(new_st, val);
                    }
                }
                else if (p_left == 1 && p_up == 1) {
                    // Case C: Two left brackets collide, change right bracket to left
                    int count = 1;
                    for (int l = j + 1; l <= m; ++l) {
                        if (get_bit(st, l) == 1) count++;
                        if (get_bit(st, l) == 2) count--;
                        if (count == 0) {
                            long long new_st = set_bit(st, l, 1);
                            new_st = set_bit(new_st, j - 1, 0);
                            new_st = set_bit(new_st, j, 0);
                            ht[nxt].insert(new_st, val);
                            break;
                        }
                    }
                }
                else if (p_left == 2 && p_up == 2) {
                    // Case D: Two right brackets collide, change left bracket to right
                    int count = 1;
                    for (int l = j - 2; l >= 0; --l) {
                        if (get_bit(st, l) == 2) count++;
                        if (get_bit(st, l) == 1) count--;
                        if (count == 0) {
                            long long new_st = set_bit(st, l, 2);
                            new_st = set_bit(new_st, j - 1, 0);
                            new_st = set_bit(new_st, j, 0);
                            ht[nxt].insert(new_st, val);
                            break;
                        }
                    }
                }
                else if (p_left == 2 && p_up == 1) {
                    // Case E: Right and left connect, naturally cancel out
                    long long new_st = set_bit(st, j - 1, 0);
                    new_st = set_bit(new_st, j, 0);
                    ht[nxt].insert(new_st, val);
                }
                else if (p_left == 1 && p_up == 2) {
                    // Case F: Endgame loop closure
                    if (i == end_x && j == end_y) {
                        // Verify that the remaining plugs are all 0 to ensure it is a unique large loop
                        long long new_st = set_bit(st, j - 1, 0);
                        new_st = set_bit(new_st, j, 0);
                        if (new_st == 0) ans += val;
                    }
                }
            }
            cur = nxt;
        }
    }

    cout << ans << "\n";
    return 0;
}

NOIP/Provincial Selection Practical Pitfall Guide

1. End of Row Not Executing Line Shift Status (Shift Operational Bug)

2. High Bit of Bitwise Operation Not Adding LL Suffix Leading to Truncation

Classic Provincial Selection/NOI Real Questions

1. Luogu P2289 [HNOI2004] Postman

2. Luogu P3190 [HNOI2007] Magical Amusement Park

Original Source: local://17.3
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS