POJ 1222 EXTENDED LIGHTS OUT 反转+点灯游戏

一、题目大意

5行6列的格子里，30盏灯，给出起始状态，让我们找到点亮哪些灯可以让这些灯全亮。（0代表亮，1代表不亮）

二、解题思路

定义一个数组f[i][j]，代表第i行第j列这个点是否被点过，1代表点过，0代表没点过。

利用二进制数的方式，枚举f[i][j]第一行的所有情况 000000 000001 000010 000011 ... 111111，

然后从第2行到第5行循环所有格子i和j，计算f[i-1]+f[i-2][j]+f[i-1][j-1]+f[i-1][j+1]和i-1 j 的起始状态，可以直到i-1 j位置的灯是否为亮的，如果它不亮，那么电亮 f[i][j]

最后判断下f[5][i]（最后一行），如果最后一行 的灯全亮，那么这是一个可行解，总和为f[i][j]求sum，如果最后一行灯不全亮，循环下一次。

判断某一个位置i j的灯是不是亮，比较简单，就是把 f[i-1][j]+f[i+1][j]+f[i][j]+f[i][j-1]+f[i][j+1]求和，判断下是不是奇数，如果时奇数，这个位置的明暗程度与起始相反，否则相同。

三、代码

#include 
using namespace std;
bool lightOn[10][10];
int revCnt[10][10], ansCnt, ans[10][10], towPow[27];
void initTwoPow()
{
    towPow[0] = 1;
    for (int i = 1; i <= 20; i++)
    {
        towPow[i] = towPow[i - 1] * 2;
    }
}
void input()
{
    ansCnt = 0x3f3f3f3f;
    int x;
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            scanf("%d", &x);
            if (x == 0)
            {
                lightOn[i][j] = true;
            }
            else
            {
                lightOn[i][j] = false;
            }
        }
    }
}
int calcRevCntAroundIJ(int i, int j)
{
    int result = revCnt[i][j];
    if (i > 1)
    {
        result += revCnt[i - 1][j];
    }
    if (j > 1)
    {
        result += revCnt[i][j - 1];
    }
    if (j < 6)
    {
        result += revCnt[i][j + 1];
    }
    if (i < 5)
    {
        result += revCnt[i + 1][j];
    }
    return result;
}
// 最后一行灯全亮吗
bool isLastLineLightOn()
{
    for (int col = 1; col <= 6; col++)
    {
        int lastLineRevCnt = calcRevCntAroundIJ(5, col);
        bool lastLineLightOn = lightOn[5][col];
        if (lastLineRevCnt % 2 != 0)
        {
            lastLineLightOn = !lightOn[5][col];
        }
        if (!lastLineLightOn)
        {
            return false;
        }
    }
    return true;
}
// 保存结果
void saveAns()
{
    int currentAnsCnt = 0;
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            currentAnsCnt += revCnt[i][j];
        }
    }
    if (currentAnsCnt >= ansCnt)
    {
        return;
    }
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            ans[i][j] = revCnt[i][j];
        }
    }
}
// solve的核心思想时第i行确定把第i-1行全部电亮
void solve()
{
    for (int i = 2; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            int beforeLineRevCnt = calcRevCntAroundIJ(i - 1, j);
            bool beforeLineLightOn = lightOn[i - 1][j];
            if (beforeLineRevCnt % 2 != 0)
            {
                beforeLineLightOn = !lightOn[i - 1][j];
            }
            if (!beforeLineLightOn)
            {
                revCnt[i][j] = 1;
            }
        }
    }
}
void flushRevCnt()
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            revCnt[i][j] = 0;
        }
    }
}
void handleFirstLineByBin(int binNum)
{
    for (int i = 5; i >= 0; i--)
    {
        int current = binNum & towPow[i];
        current = current >> i;
        if (current == 1)
        {
            revCnt[1][6 - i] = 1;
        }
        else
        {
            revCnt[1][6 - i] = 0;
        }
    }
}
void outputAns()
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            if (j == 6)
            {
                printf("%d\n", ans[i][j]);
            }
            else
            {
                printf("%d ", ans[i][j]);
            }
        }
    }
}
int main()
{
    initTwoPow();
    int t = 0;
    scanf("%d", &t);
    for (int m = 1; m <= t; m++)
    {
        input();
        int base = 1024;
        for (int i = 0; i < towPow[6]; i++)
        {
            int binNum = base + i;
            flushRevCnt();
            handleFirstLineByBin(binNum);
            solve();
            if (isLastLineLightOn())
            {
                saveAns();
            }
        }
        printf("PUZZLE #%d\n", m);
        outputAns();
    }
    return 0;
}