2018 0CTF mayagame 插头dp

writeup是说：插头dp模板题

http://westerns.tokyo/writeups/0ctf2018quals.html#maya-game

代码添加注释：

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <map>
using namespace std;

int N, M;

vector<string> MAP;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

vector<vector<vector<map<vector<int>,int64_t> > > > dp;

void normalize(std::vector<int> &connection, int &left) {
    vector<int> mp(connection.size() + 2, -1);
    //vector<int> a(10, 1);
    //声明一个初始大小为10，且初始值为1
    //memset(mp,-1)
    mp[0] = 0;
    int k = 1;
    for (int i = 0; i < connection.size(); i++) {
        if (connection[i] != 0) {
            assert(connection[i] < mp.size());
            if (mp[connection[i]] == -1) {
                mp[connection[i]] = k++;
            }
        }
    }
    if (left != 0) {
        if (mp[left] == -1) {
            mp[left] = k;
        }
    }

    for (int i = 0; i < connection.size(); i++) {
        connection[i] = mp[connection[i]];
    }
    left = mp[left];
}

int64_t rec(int y, int x, const std::vector<int> connection, int left) {
    assert(connection.size() == N);
    if (y == N) {
        // 終了条件
        for (int i = 0; i < N; i++) {
            if (connection[i] != 0) {
                // 上に接続がある: Fail
                // 上有连接：fail
                return 0;
            }
        }
        // 上に接続がなければひとまず成功とする
        // 若没有上连接，则先成功
        // 最后一列都成功匹配
        return 1;
    }
    //记忆化搜索
    //y：列坐标
    //x：横坐标
    //left：剩下的是哪一个没有匹配
    //connection：上面的连接情况
    if (dp[y][x][left].count(connection)) {
        //count统计等于某个值的对象的个数
        return dp[y][x][left][connection];
    }

    cout << "REC: (" << x << ", " << y << ") : " << left << " {";
    for(int i = 0; i < connection.size(); i++) {
        cout << connection[i] << ", ";
    }
    cout << "}" << endl;
    /*
    cout << "\tcc: [";
    for(int i = 0; i < connection_count.size(); i++) {
        cout << connection_count[i] << ", ";
    }
    cout << endl;
    */
    int ny = y, nx = x + 1;
    //下一个节点
    if (nx == N) {
        ny++;
        nx = 0;
    }
    // cout << "s:" << y << "," << x << endl;

    int64_t ret = 0;
    const char cur = MAP[y][x];
    // cur是下一个字符
    if (cur == '#') {
        if (left != 0) {
            // 左側からの接続があるので駄目
            // 因为有来自左边的连接，所以不行
            ret = 0;
        } else if (connection[0] != 0) {
            // 上からの接続があるので駄目
            // 上面有连接，所以不行
            ret = 0;
        } else {
            // 次のコネクションを作る
            // 制作下面的关系
            // 線は引かずに次に進むしかない
            // 只能继续走下去
            vector<int> next_connection = connection;
            next_connection.erase(next_connection.begin());
            //删除第一个元素
            next_connection.push_back(0);
            //在末尾添加一个0
            ret = rec(ny, nx, next_connection, 0);
        }
    } else if (cur == 'X') {
        // 次のコネクションを作る
        // 制作下面的关系
        if (left != 0 && connection[0] != 0) {
            // 上と左から来ている場合は二本引かれるためアウト
            // 在上面和左来的情况下，因为被吸引而出局
            ret = 0;
        } else if (left != 0) {
            assert(connection[0] == 0);
            // 左からのみ来ている場合
            // 从左边来的情况
            // 接続を追加する
            // 追加连接
            vector<int> next_connection = connection;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(0);
            //删除第一个元素，末尾添加一个0
            int next_left = 0;
            normalize(next_connection, next_left);
            ret = rec(ny, nx, next_connection, next_left);
        } else if (connection[0] != 0) {
            assert(left == 0);
            // 上からのみ来ている場合
            // 从上面来的情况
            vector<int> next_connection = connection;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(0);
            int next_left = 0;
            normalize(next_connection, next_left);
            ret = rec(ny, nx, next_connection, next_left);
        } else {
            // 右か下に接続する
            // 连接到右下角
            // 右に接続する場合
            int next_number = max(left, *max_element(connection.begin(), connection.end())) + 1;
            ret = 0;
            if (x < N - 1) {
                vector<int> next_connection = connection;
                int next_left = next_number;
                next_connection.erase(next_connection.begin());
                next_connection.push_back(0);
                // cout << x << "," << y << "," << left << ":" << (next_connection_count.size()) << "," << (next_number + 1) << endl;
                normalize(next_connection, next_left);
                ret += rec(ny, nx, next_connection, next_left);
            }
            if (y < N - 1) {
                // 下に接続する
                // 连接到下面
                vector<int> next_connection = connection;
                int next_left = 0;
                next_connection.erase(next_connection.begin());
                next_connection.push_back(next_number);
                normalize(next_connection, next_left);
                ret += rec(ny, nx, next_connection, next_left);
            }
        }
    } else if (cur == '.') {
        // 次のコネクションを作る
        // 制作下面的关系
        // 上→下
        if (connection[0] != 0 && left == 0 && y < N - 1) {
            // 上からの接続があり右側から接続がない
            // 从上面有连接，右边没有连接
            vector<int> next_connection = connection;
            int next_left = 0;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(connection[0]);
            ret += rec(ny, nx, next_connection, next_left);
        }
        // 上から右
        // 从上向右
        if (connection[0] != 0 && left == 0 && x < N - 1) {
            // 上からの接続があり右側から接続がない
            // 从上面有连接，右边没有连接
            vector<int> next_connection = connection;
            int next_left = connection[0];
            next_connection.erase(next_connection.begin());
            next_connection.push_back(0);
            normalize(next_connection, next_left);
            ret += rec(ny, nx, next_connection, next_left);
        }

        // 左→下
        if (connection[0] == 0 && left != 0 && y < N - 1) {
            // 上からの接続があり右側から接続がない
            // 从上面有连接，右边没有连接
            vector<int> next_connection = connection;
            int next_left = 0;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(left);
            normalize(next_connection, next_left);
            ret += rec(ny, nx, next_connection, next_left);
        }
        // 左から右
        // 从左到右
        if (connection[0] == 0 && left != 0 && x < N - 1) {
            vector<int> next_connection = connection;
            int next_left = left;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(0);
            normalize(next_connection, next_left);
            ret += rec(ny, nx, next_connection, next_left);
        }
        // 左上
        if (connection[0] != 0 && left != 0) {
            if (connection[0] == left) {
                // 既に接続ずみなので置けない
                // 已经连接不了，放不下
            } else {
                // 左と上を接続
                // 把左边和上面连接起来
                vector<int> next_connection = connection;
                int next_left = 0;
                next_connection.erase(next_connection.begin());
                next_connection.push_back(0);
                // Merge
                // 合并
                for (int i = 0; i < N; i++) {
                    if (next_connection[i] == left) {
                        next_connection[i] = connection[0];
                    }
                }
                // Normalize
                // 
                normalize(next_connection, next_left);
                ret += rec(ny, nx, next_connection, next_left);
            }
        }
        // 右上
        if (connection[0] == 0 && left == 0 && x < N - 1 && y < N - 1) {
            int next_number = max(left, *max_element(connection.begin(), connection.end())) + 1;
            ret = 0;
            vector<int> next_connection = connection;
            int next_left = next_number;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(next_number);
            normalize(next_connection, next_left);
            ret += rec(ny, nx, next_connection, next_left);
        }
        // 何もしない
        // 什么也不干
        if (connection[0] == 0 && left == 0) {
            vector<int> next_connection = connection;
            int next_left = 0;
            next_connection.erase(next_connection.begin());
            next_connection.push_back(0);
            normalize(next_connection, next_left);
            ret += rec(ny, nx, next_connection, next_left);
        }
    } else {
        //std::cout << "Invalid Error" << endl;
        //throw std::runtime_error("Invalid Map data");
        cout << "Input Error" << endl;
    }
    return dp[y][x][left][connection] = ret;
}

//
// Upとの接続状況
// 与up的连接状况
//
// Yes
// +-----+
// |+---+|
// ||+-+||
// |||#|X|
// XXX#+-+
//
// Split [1,1,1,1,1,1,1]
//
int main() {
    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF){
        //cin >> N >> M;
        MAP.clear();
        dp.clear();
        MAP.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> MAP[i];
        }
        //X:0->N-1
        //Y:0->N-1
        dp.resize(N);
        for( int i = 0; i < dp.size(); i++) {
            dp[i].resize(N);
            for(int j = 0 ; j < dp[i].size(); j++) {
                dp[i][j].resize(N + 3);
            }
        }
        vector<int> connection(N);
        //connection.clear();
        int64_t ret = rec(0, 0, connection, 0);
        cout << ret << endl;
    }
    return 0;
}

附上数据：

4 4
XX..
....
..##
.X.X

7 6
.......
...X.X.
.#..X..
....X..
..#....
X.X...#
.......

4 6
#XX.
X..X
XX#.
..#.

4 6
.XX#
X#.X
X.X.
....

3 4
#XX
.X.
#.X

4 6
X.XX
X.#X
..X.
#...

5 6
..#..
..#.X
...XX
..X..
X..X.

4 6
X#.X
..X.
..X.
#.XX

4 4
...X
X.X#
#...
X..#