题解

这道题目有三个状态条件值得考虑：

每一个开关被按0次或者1次才有意义，如果超过1次，那么等同于按0或1次。
最终的结果与按的顺序无关
因为2，所以可以人为地规定比较合理的顺序。
现在以每一行为顺序。先经过一波操作把上一行全部搞成1，然后看这行，如果有0，那么只能按下一行的，以此类推。

起始状态难以把握，但是我们可以使用暴力枚举。
暴力地把第一行分割为2^5种情况。

代码



#include <bits/stdc++.h>

using namespace std;

int origin[7][7];

int tmp[7][7];

inline void op(int i, int j)

{

    tmp[i][j] = (tmp[i][j]+1)%2;

    tmp[i+1][j] = (tmp[i+1][j]+1)%2;

    tmp[i-1][j] = (tmp[i-1][j]+1)%2;

    tmp[i][j+1] = (tmp[i][j+1]+1)%2;

    tmp[i][j-1] = (tmp[i][j-1]+1)%2;

}

int baoli = 0;

int main()

{

    int T;

    cin >> T;

    while(T--)

    {

        for(int i = 1; i <= 5; i++)

        {

            char buf[12];

            scanf("%s", buf+1);

            for(int j = 1; j <= 5; j++)

                origin[i][j] = buf[j]-'0';

        }

        int ans = 0x3f3f3f3f;

        for(baoli = 0; baoli < 32; baoli++)

        {

            int cnt = 0;

            for(int i = 1; i <= 5; i++)

                for(int j = 1; j <= 5; j++)

                    tmp[i][j] = origin[i][j];

            for(int i = 0; i < 5; i++)

            {

                if((baoli>>i)&1)

                {

                    op(1, i+1);

                    cnt++;

                }

            }

            for(int i = 1; i <= 4; i++)

                for(int j = 1; j <= 5; j++)

                {

                    if(tmp[i][j]==0)

                    {

                        op(i+1,j);

                        cnt++;

                    }

                    if(cnt > 6)

                        break;

                }

            if(cnt>6) continue;

            for(int i = 1; i <= 5; i++)

            {

                if(tmp[5][i]==0)

                    goto lab1;

            }

            ans = min(ans, cnt);

            lab1:

            ;

        }

    if(ans == 0x3f3f3f3f) printf("-1\n");

    else printf("%d\n", ans);

    }

    return 0;

}

巴特西

ACWing95. 费解的开关

题解

代码

最新文章

热门文章