除 #1 #3 #9 WA 求助, 悬二关

#include <bits/stdc++.h>
const int MAXN = 120, MAXM = 20, MAXVAL = 3000;

int N, M;
int Map[MAXN][MAXM];

std::vector< std::pair<int, int> > State[MAXM];

class Sol_Class
{
private:
    /*判断状态合法性*/
    bool Check(int pos, int S1, int S2) {
        /*判断 line1 的最上端*/
        int line1UP = S1 >> pos;
        if ((line1UP << 1) & line1UP) return false;
        if ((line1UP << 2) & line1UP) return false;

        int line1DOWN = S1 - (line1UP << pos);
        int line2UP = S2 >> pos;
        int line12 = line1DOWN + (line2UP << pos);
        if ((line12 << 1) & line12) return false;
        if ((line12 << 2) & line12) return false;

        int line2DOWN = S2 - (line2UP << pos);
        if ((line2DOWN << 1) & line2DOWN) return false;
        if ((line2DOWN << 2) & line2DOWN) return false;

        if (S1 & S2) return false;

        return true;
    }

public:
    /*初始化每个位置合法的状态*/
    void init_state()
    {
        /*当前位置, 统一按照由右至左, 由下到上按照低位到高位摆放*/
        for (int i = 0; i < M; i++) {
            for (int S1 = 0; S1 < (1 << M); S1++) {
                for (int S2 = 0; S2 < (1 << M); S2++) {
                    if (Check(i, S1, S2))
                        State[i].push_back({S1, S2});
                }
            }
        }
    }

    int f[2][MAXVAL][MAXVAL];

    /*状态压缩 dp 的转移*/
    void solve()
    {
        int res = 0;
        memset(f, 0, sizeof(f));
        f[res][0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                res++; res %= 2;
                for (int u = 0; u < (1 << M); u++)
                    for (int v = 0; v < (1 << M); v++)
                        f[res][u][v] = 0;

                for (int k = 0; k < State[j].size(); k++) {
                    int S1 = State[j][k].first, S2 = State[j][k].second;

                    /*不取*/
                    int nowS1 = (S1 << 1) | ((S2 >> (M - 1)) & 1);
                    int nowS2 = (S2 << 1);
                    nowS1 = nowS1 & (~(1 << M));
                    nowS2 = nowS2 & (~(1 << M));
                    f[res][nowS1][nowS2] = std::max(f[res][nowS1][nowS2], f[1 - res][S1][S2]);
                    int tmp; if (j == 0) tmp = 0; else if(j == 1) tmp = 1; else tmp = 3;
                    if ((S1 >> (M - 1)) & 1 || (S2 >> (M - 1)) & 1 || S2 & tmp || !Map[i][j]) continue;

                    nowS1 = (S1 << 1) | ((S2 >> (M - 1)) & 1);
                    nowS2 = (S2 << 1) | 1;
                    nowS1 = nowS1 & (~(1 << M));
                    nowS2 = nowS2 & (~(1 << M));
                    f[res][nowS1][nowS2] = std::max(f[res][nowS1][nowS2], f[1 - res][S1][S2] + 1);
                }
            }
        }

        int Ans = 0;
        for (int S1 = 0; S1 < (1 << M); S1++) {
            for (int S2 = 0; S2 < (1 << M); S2++) {
                Ans = std::max(Ans, f[res][S1][S2]);
            }
        }

        printf("%d", Ans);
    }

} Sol;

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char Now; std::cin >> Now;
            Map[i][j] = (Now == 'P');
        }
    }

    Sol.init_state();
    Sol.solve();

    return 0;
}

过掉了一些 hack 和 Sub1