Algorithm/plug-dp/main.cc

#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define mo 590027
using namespace std;

int n, m, mapx[20][20] = {0}, endx, endy;
ll all_ans = 0, dp[2][600000] = {0};

int bits[28] = {0};

int state[2][600000] = {0}, tots[2] = {0};
int pre = 1, cnt = 0;

struct hash_table {
  int pre, to;
} idx[600000] = {0};
int ptr[600000] = {0}, at = 0;

inline void readit() {
  cin >> n >> m;
  char cht = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      mapx[i][j] = 1;
      endx = i;
      endy = j;
    }
}
inline void init_bits() {
  for (int i = 1; i <= 25; i++)
    bits[i] = (i << 1);
}

inline void hah(int sta, ll val) {
  int key = sta % mo;
  for (int prex = ptr[key]; prex; prex = idx[prex].pre)
    if (state[cnt][idx[prex].to] == sta) {
      dp[cnt][idx[prex].to] += val;
      return;
    }
  tots[cnt]++;
  state[cnt][tots[cnt]] = sta;
  dp[cnt][tots[cnt]] = val;

  idx[++at].pre = ptr[key];
  idx[at].to = tots[cnt];
  ptr[key] = at;
}

inline void calc_dp() {
  tots[cnt] = 1;
  dp[cnt][1] = 1;
  state[cnt][1] = 0;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= tots[cnt]; j++)
      state[cnt][j] <<= 2; //!!!

    for (int j = 1; j <= m; j++) {
      at = 0;
      memset(ptr, 0, sizeof ptr); // clear hash_table
      swap(pre, cnt);             // rolling
      tots[cnt] = 0;              // clear state counter

      int nowsta, is_d, is_r;
      ll nowans;
      for (int k = 1; k <= tots[pre]; k++) {
        nowsta = state[pre][k], nowans = dp[pre][k]; // get previous
                                                     // state&answer
        is_d = (nowsta >> bits[j]) % 4,
        is_r = (nowsta >> bits[j - 1]) % 4; // get current plugs

        if (!mapx[i][j]) // case 0
        {
          if ((!is_d) && (!is_r))
            hah(nowsta, nowans);
        }

        else if ((!is_d) && (!is_r)) // case 1
        {
          if (mapx[i + 1][j] && mapx[i][j + 1])
            hah(nowsta + (1 << bits[j - 1]) + 2 * (1 << bits[j]), nowans);
        }

        else if ((!is_d) && is_r) // case 2
        {
          if (mapx[i + 1][j])
            hah(nowsta, nowans); // go down
          if (mapx[i][j + 1])
            hah(nowsta - is_r * (1 << bits[j - 1]) + is_r * (1 << bits[j]),
                nowans); // go right
        }

        else if (is_d && (!is_r)) // case 3
        {
          if (mapx[i][j + 1])
            hah(nowsta, nowans); // go right
          if (mapx[i + 1][j])
            hah(nowsta - is_d * (1 << bits[j]) + is_d * (1 << bits[j - 1]),
                nowans); // go down
        }

        else if (is_d == 1 && is_r == 1) // case 4
        {
          int count = 1;
          for (int l = j + 1; l <= m; l++) {
            if ((nowsta >> bits[l]) % 4 == 1)
              count++;
            else if ((nowsta >> bits[l]) % 4 == 2)
              count--;
            if (!count) {
              hah(nowsta - (1 << bits[l]) - (1 << bits[j]) - (1 << bits[j - 1]),
                  nowans);
              break;
            }
          }
        }

        else if (is_d == 2 && is_r == 2) // case 5
        {
          int count = 1;
          for (int l = j - 2; l >= 0; l--) {
            if ((nowsta >> bits[l]) % 4 == 1)
              count--;
            else if ((nowsta >> bits[l]) % 4 == 2)
              count++;
            if (!count) {
              hah(nowsta - 2 * (1 << bits[j]) - 2 * (1 << bits[j - 1]) +
                      (1 << bits[l]),
                  nowans);
              break;
            }
          }
        }

        else if (is_d == 1 && is_r == 2) // case 6
          hah(nowsta - 2 * (1 << bits[j - 1]) - (1 << bits[j]), nowans);

        else if (is_r == 1 && is_d == 2) // case 7
          if (i == endx && j == endy)
            all_ans += (ll)nowans;
      }
    }
  }
}

int main() {
  readit();
  init_bits();
  calc_dp();
  // 无方向不用乘 2
  cout << all_ans * 2 << endl;
  return 0;
}