牛可乐的翻转游戏 60%

思路

这个题感觉只能枚举所有的翻转模式

但是这样明显会超时, 有

然后想了想,其实可以只枚举第一行的所有状态

然后找到一个不会影响前面行的翻转模式, 记录最少的翻转次数即可

N * M = 100 * 10 , 刚好 时间复杂度

翻转模式 : 对于上一行, 没有到位的棋子 , 逐个翻转下一行 , 最后再检查最后一行是不是就位即可

    auto get = [&](int st, int v)
    {
        int cnt = 0;
        b = a;
        for (int i = 0; i < m; i++)
        {
            if (st & (1 << i)) // 从第1行开始翻转
            {
                cnt++; // 翻转第i位
                // debug(b);
                change(1, i);
            }
        }

        for (int c = 2; c <= n; c++)
        {
            for (int r = 1; r <= m; r++)
            {
                if (b[c - 1][r] != v)
                {
                    cnt++;
                    change(c, r);
                }
            }
        }

        for (int i = 1; i <= m; i++)
            if (b[n][i] != v)
                return inf;

        return cnt;
    };

60% 代码 实在没看出来哪里错了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long
const int inf = 0x3f3f3f3f;
int n, m;
void debug(vector<vector<bool>> &s)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << s[i][j] << " ";
        }
        cout << endl;
    }
}
int32_t main()
{

    cin >> n >> m;
    vector<vector<bool>> a(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char ch;
            cin >> ch;
            a[i][j] = ch - '0';
        }
    // debug(a);
    auto b = a;
    auto change = [&](int x, int y)
    {
        int dx[] = {0, 0, 1, -1, 0};
        int dy[] = {0, 1, 0, 0, -1};

        for (int i = 0; i < 5; i++)
        {
            int xx = dx[i] + x, yy = dy[i] + y;
            if (1 <= xx && xx <= n && 1 <= yy && yy <= m)
                b[xx][yy] = !b[xx][yy];
        }
    };
    auto get = [&](int st, int v)
    {
        int cnt = 0;
        b = a;
        for (int i = 0; i < m; i++)
        {
            if (st & (1 << i)) // 从第1行开始翻转
            {
                cnt++; // 翻转第i位
                // debug(b);
                change(1, i);
            }
        }

        for (int c = 2; c <= n; c++)
        {
            for (int r = 1; r <= m; r++)
            {
                if (b[c - 1][r] != v)
                {
                    cnt++;
                    change(c, r);
                }
            }
        }

        for (int i = 1; i <= m; i++)
            if (b[n][i] != v)
                return inf;

        return cnt;
    };
    int ans = inf + 1;
    for (int i = 0; i < (1 << m); i++)
    {
        ans = min(ans, get(i, 0));
        ans = min(ans, get(i, 1));
    }
    if (ans == inf)
        cout << "Impossible";
    else
        cout << ans;
    return 0;
}