题目描述

blablabla

样例

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 100000;

char g[10][10];
int dx[5] = {0,-1,0,1,0} , dy[5] = {0,0,1,0,-1};//表示不同的方位: 自身, 左, 上, 右, 下.  

//根据改变的位置改变相应的值
void turn(int x, int y)
{
    for(int i = 0; i < 5; i ++)
    {
        int a = x + dx[i], b = y +dy[i];
        // 合法的范围内进行调整
        if(a >= 0 && a < 5 && b >= 0 && b < 5)
        {
            //g[a][b] = '0' + !(g[a][b] - '0');
            g[a][b] ^= 1;
        }
    }
}


int work()
{
    int ans = INF;
    // 对第一行的 32(1 << 5)次枚举(暴力) 涵盖了该问题的整个状态空间
    for(int k = 0; k < 1 << 5; k ++)
    {
        int res = 0;
        char backup[10][10];
        memcpy(backup, g, sizeof g);

        //对于第 0 行的调整.
        for(int j = 0; j < 5; j ++)
        {
            // k = 0b 代表 0号位 不做出改变
            // k = 1b 代表 0号位 不做出改变
            // k = 10b 代表 0号位 不做出改变, 1号位 做出改变
            // k = 11b 代表 0号位 和 1号位 做出改变.....以此类推.代表32种可能操作.
            if(k >> j & 1)
            {
                res ++;
                turn(0,j);
            }
        }

        //下面的代码只是根据你的选择, 比如 你选择 第一行的第0号位置 改变,其他都不做出改变, 后面就跟你的判断相应的做出变化
        //若遍历到最后一行不能完成全为1的状态 或者 次数超过6, 这次的判断就是false

        //但是只要你的其中一个判断可以导致整个矩阵可以转换为全为1的状态(且次数不超过6) 就是操作正确.
        //对于1 - 4的调整. 可以根据下面的turn(i + 1, j)看出
        for(int i = 0; i < 4; i ++)
        {
            for(int j = 0; j < 5; j ++)
            {
                if(g[i][j] == '0')
                {
                    res ++;
                    turn(i + 1, j);
                }
            }
        }

        //根据 最后一行 进行判断整个矩阵是否全为1.
        bool is_successful = true;
        for(int j = 0; j < 5; j ++)
        {
            if(g[4][j] == '0')
            {
                is_successful = false;
                break;
            }
        }

        if(is_successful) ans = min(ans, res);
        memcpy(g, backup, sizeof g);
    }
    //判断次数
    if(ans > 6) return -1;
    return ans;
}


int main()
{
    int metric;
    cin >> metric;

    while(metric --)
    {
        for(int i = 0; i < 5; i ++) cin >> g[i]; //一次性输入一行
        cout << work() <<endl;
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla