标签：cnt YetAnotherBoardGame rep int vec cst op

Topcoder #搜索

经典套路，我们发现枚举第一行后剩余的其实是确定的

那么枚举并爆搜即可

时间复杂度是 \(3^k\) 因为列的限制

// Author: xiaruize
const int N = 13 + 10;

int n, m;
bool s[N][N], bck[N][N];
int op[N];

void upd(int x, int y, int ty)
{
    if (ty == 1)
        s[x][y] ^= 1;
    if (x < n - 1)
        s[x + 1][y] ^= 1;
    if (y < m - 1)
        s[x][y + 1] ^= 1;
    if (x)
        s[x - 1][y] ^= 1;
    if (y)
        s[x][y - 1] ^= 1;
}

int res = INF;

void dfs(int x, int cst)
{
    int bop[N];
    // debug(x, op);
    if (x == n)
    {
        bool flag = true;
        rep(i, 0, m - 1) flag &= (!s[n - 1][i]);
        if (flag)
        {
            res = min(res, cst);
            // debug(cst);
        }
        return;
    }
    bool fl1 = true, fl2 = true;
    rep(i, 0, m - 1)
    {
        if (s[x - 1][i])
        {
            if (op[i] == 1)
                fl2 = false;
            if (op[i] == 2)
                fl1 = false;
        }
    }
    if (!fl1 && !fl2)
        return;
    memcpy(bop, op, sizeof(op));
    if (fl1)
    {
        int cnt = 0;
        vector<int> vec;
        vec.clear();
        rep(i, 0, m - 1)
        {
            if (s[x - 1][i])
            {
                op[i] = 1;
                vec.push_back(i);
                upd(x, i, 1);
                cnt++;
            }
        }
        dfs(x + 1, cst + cnt);
        for (auto v : vec)
            upd(x, v, 1);
        memcpy(op, bop, sizeof(op));
    }
    if (fl2)
    {
        int cnt = 0;
        vector<int> vec;
        vec.clear();
        rep(i, 0, m - 1)
        {
            if (s[x - 1][i])
            {
                op[i] = 2;
                vec.push_back(i);
                upd(x, i, 2);
                cnt++;
            }
        }
        dfs(x + 1, cst + cnt);
        for (auto v : vec)
            upd(x, v, 2);
        memcpy(op, bop, sizeof(op));
    }
}

void solve()
{
    cin >> n;
    rep(i, 0, n - 1)
    {
        string str;
        cin >> str;
        m = str.size();
        rep(j, 0, m - 1) s[i][j] = (str[j] != 'B');
    }
    // debug(s);
    memcpy(bck, s, sizeof(s));
    mms(op, 0);
    rep(i, 1, 2)
    {
        rep(msk, 0, (1 << m) - 1)
        {
            mms(op, 0);
            memcpy(s, bck, sizeof(s));
            rep(j, 0, m - 1)
            {
                if (msk & (1 << j))
                {
                    op[j] = i;
                    upd(0, j, i);
                }
                else
                    op[j] = 0;
            }
            dfs(1, __builtin_popcount(msk));
            rep(j, 0, m - 1) if (msk & (1 << j)) upd(0, j, i);
        }
        mms(op, 0);
        memcpy(s, bck, sizeof(s));
    }
    if (res <= n * m)
        cout << res << endl;
    else
        cout << "-1" << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

注意递归变量不要开全局！

标签：cnt,YetAnotherBoardGame,rep,int,vec,cst,op
From： https://www.cnblogs.com/xiaruize/p/18136775