USTCOJ 1240 黑屋 非位運算版

USTCOJ 1240，黑屋：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1240

該題采用暴力枚舉的方式求出關燈所需的最少步數。其中press數組标記了了在每一次嘗試關閉所有燈時需要按下的按鈕。

程式将原有的2^(m*n)中可能的按按鈕操作縮減為了2^m次方種按按鈕操作。大大縮減了搜尋空間。對于每一種按按鈕操作，均調用turnOffLight函數嘗試關燈，若關燈成功，傳回true，不能将所有等關閉，則傳回false。turnOffLight函數執行完後，可通過press數組讀取本次關燈所需按下的按鈕。

該解法的加速增強版請參考：http://blog.csdn.net/l03071344/article/details/8816508

/***********
*原作者：liujianhua
*修改注釋：lance
***********/
#include <cstdio>
#include <cstring>
#define MAXLEN 100
#define MAXWID  15

//數組開大一些，省去邊界判斷
int puzzle[MAXLEN + 5][MAXWID + 5];
char press[MAXLEN + 5][MAXWID + 5];
int n, m;

bool turnOffLight()
{
    int c, r;
    for(r = 1; r < n; ++r)
    {
        for(c = 1; c < m + 1; ++c)
            press[r + 1][c] = (puzzle[r][c] + press[r][c] + press[r - 1][c] + press[r][c - 1] + press[r][c + 1]) % 2;
    }
    for(c = 1; c < m + 1; ++c)
    {
        if((press[n][c - 1] + press[n][c] + press[n][c + 1] + press[n - 1][c]) % 2 != puzzle[n][c])
            return false;
    }
    return true;
}

//将計數部分剝離為一個函數
int count_step()
{
    int r, c, sum = 0;
    for(r = 1; r <= n; r++)
    {
        for(c = 1; c <= m; ++c)
        {
            if(press[r][c] == 1)
                ++sum;
        }
    }
    return sum;
}

int enumate()
{
    int minsteps = -1;
    int c = 0;
    while (1)
    {
        //每次while循環guess函數總會執行
		//從press[1]全0開始，即從不管第一行任何燈開始
        if (turnOffLight())
        {
            int step = count_step();
            if (minsteps == -1 || minsteps > step)
                minsteps = step;
        }
        //對press[1]數組進行二進制加法，枚舉所有可能的關燈方式
        press[1][1]++;
        c = 1;
        while (press[1][c] > 1)
        {
            press[1][c++] = 0;
            press[1][c]++;      //進位
        }
        //通過判斷進位是否已經到c，來确定是否已經枚舉完2^m種可能
        if (c == m + 1)
            break;
    }
    return minsteps;
}

main()
{
    freopen("1240.in", "r", stdin);
    freopen("1240.out", "w", stdout);
    while((scanf("%d %d", &n, &m)) != EOF)
    {
    	//需要對press數組初始化，清除上一輪對press數組的設定
        memset(&press[0][0], 0, (n + 1) * (m + 1)); 
        int i, j;
        for(i = 1; i <= n; ++i)
        {
            for(j = 1; j <= m; ++j)
            {
                scanf("%d", &puzzle[i][j]);
                if(puzzle[i][j] == 1)
                    puzzle[i][j] = 0;
                else if(puzzle[i][j] == 0)
                    puzzle[i][j] = 1;
            }
        }
        //枚舉所有可能的開燈方式，傳回可能的最小步數
        int sum = enumate();
        if (sum == -1)
            printf("no solution\n");
        else
            printf("%d\n", sum);
    }
    return 0;
}