题解 P2040 【打开所有的灯】

2018-04-29 19:51:55


此题甚水。首先要明确:同一盏灯操作一次就够了!!!因为灯的状态与开关灯的次序无关!

接着就好办了:用一个int记录下一个二进制数,代表对灯光的操作,如样例,最优操作是动第一与第五盏灯,操作码为000010001(2) 即17. 然后这个九位二进制数到范围在0~1023之间,慢慢去凑状态吧~

最后贴代码:

#include <bits/stdc++.h>
using namespace std;
int a[5][5],b[5][5],dx[] = {0,1,0,-1},dy[] = {1,0,-1,0},ans = INT_MAX;
void chk(int num) //这是个检查的函数
{
    int cnt = 0;
    for (int i = 0;i < 3;i++)
        for (int j = 0;j < 3;j++)
        {
            if (num % 2) //此灯要戳一下
            {
                ++cnt;
                b[i][j] = !b[i][j];
                for (int k = 0;k < 4;k++)
                {
                    int nx = i + dx[k],ny = j + dy[k];
                    if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3)
                        b[nx][ny] = !b[nx][ny];
                }
            }
            num /= 2;//向下一位进军
        }
    for (int i = 0;i < 3;i++)
        for (int j = 0;j < 3;j++) 
            if (b[i][j] == 0) return;
    ans = min(ans,cnt);
}
int main()
{
    for (int i = 0;i < 3;i++)
        for (int j = 0;j < 3;j++)
            scanf("%d",&a[i][j]);
    int mx = pow(2,10);
    for (int i = 0;i < mx;i++)//凑状态码
    {
        for (int j = 0;j < 3;j++)
            for (int k = 0;k < 3;k++) b[j][k] = a[j][k];//不想要用memcpy,反正时间差不多
        chk(i);
    }
    printf("%d",ans);
    return 0;
}