0201 费解的开关

谁践踏了优雅 2022-01-22 05:57 223阅读 0赞

题目链接：[http://contest-hunter.org:83/contest/0x00「基本算法」例题/0201 费解的开关][http_contest-hunter.org_83_contest_0x00_0201]

本题有三个性质。只要把这三个性质找出来。那么本题也就比较简单了。  
1，每个位置至多只会被点击一次。  
2，若固定了第一行（不能在改变第一行），则满足题意的点击方案至多只有一种。其原因是：当第i行某一位为1时，若前i行已被固定，只能点击第i+１行该位置上的数字才能使第ｉ行的这一位变为１.  
３，点击的先后顺序不影响最终的结果。

因为题目是一个５×５的矩阵。所以我们先考虑第一行应该是怎么点击。然后在依次向下枚举。  
一个５×５的矩阵，第一行的点击方案最多只有２^5种。我们利用二进制的性质，可以直接用位来表示哪些是被点击的，哪些是未点击的。然后在通过不断向下枚举。到第5行的时候看第5行是不是都为1.因为第5行的状态是无非被改变了的。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int n,Hash[1 << 6],cont,minx;
    int Graph[10][10],b[10][10];
    
    int check(int x)
    {
        for(int i = 0; i < 6; i ++)
            Hash[1 << i] = i;
        return Hash[x];
    }
    void change(int x)
    {
        while(x)
        {
            int pos = check(x & (-x));
            b[1][pos + 1] ^= 1;
            b[1][pos] ^= 1;
            b[1][pos + 2] ^= 1;
            b[2][pos + 1] ^= 1;
            cont ++;
            x &= (~((1 << pos)));
        }
        return ;
    }
    
    void dfs(int row,int cnt)
    {
        if(row == 5)
        {
            for(int i = 1; i <= 5; i ++)
                if(b[5][i] == 0)
                   return ;
            minx = min(minx,cnt);
          //  printf("minx = %d\n",minx);
            return ;
        }
       // printf("row = %d cnt = %d\n",row,cnt);
        int mark = 1;
        for(int i = 1; i <= 5; i ++)
        {
            if(b[row][i] == 0)
            {
                b[row][i] ^= 1; //上下左右要考虑周全
                b[row + 1][i] ^= 1;
                b[row + 1][i + 1] ^= 1;
                b[row + 1][i - 1] ^= 1;
                b[row + 2][i] ^= 1;
                cnt ++;
            }
        }
        dfs(row + 1,cnt);
        return ;
    }
    
    int main()
    {
        scanf("%d",&n);
        while(n --)
        {
            cont = 0; minx = 1000;
            for(int i = 0; i < 10; i ++)
                for(int j = 0; j < 10; j ++)
                    Graph[i][j] = 0;
            for(int i = 1; i <= 5; i ++)
                for(int j = 1; j <= 5; j ++)
                    scanf("%1d",&Graph[i][j]);
            for(int i = 0; i < 32; i ++)//这里没到32  注意
            {
                cont = 0;
             //   printf("i = %d\n",i);
                for(int i = 1; i <= 5; i ++)
                    for(int j = 1; j <= 5; j ++)
                        b[i][j] = Graph[i][j];
                change(i);
                dfs(1,cont);
            }
            if(minx <= 6)
                printf("%d\n",minx);
            else
                printf("-1\n");
        }
    }

[http_contest-hunter.org_83_contest_0x00_0201]: http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0201%20%E8%B4%B9%E8%A7%A3%E7%9A%84%E5%BC%80%E5%85%B3