和这个类似的有
http://www.51nod.com/Challenge/Problem.html#problemId=2615

思路很简单,枚举第一行,判断最后一行,记录最小值就好了。

#include <iostream>
#include <cstring>
 
using namespace std;
 
int a[20][20],b[20][20];
int f[20][20],ans[20][20],fNum,aNum,n,m;
 
//翻转
void tranc(int x,int y){
    fNum ++;
    f[x][y] = 1;
    b[x][y] = 1-b[x][y];
    b[x-1][y] = 1-b[x-1][y];
    b[x+1][y] = 1-b[x+1][y];
    b[x][y-1] = 1-b[x][y-1];
    b[x][y+1] = 1-b[x][y+1];
}
 
//记录答案
void record(){
    aNum = fNum;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            ans[i][j] = f[i][j];
        }
    }
}
 
int main()
{
    //输入数据
    cin >> m >> n;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            cin >> a[i][j];
        }
    }
    int t = 1 << n;
    aNum = 10000;
    //尝试第一行的所有可能
    for(int loop = 0; loop < t;  loop ++){
        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                b[i][j] = a[i][j];
            }
        }
        fNum = 0;
        int moveN = loop;
        memset(f,0,sizeof(f));
        //翻转第一行
        for(int j = 1; j <= n; j ++){
            if(moveN & 1) tranc(1,j);
            moveN = moveN >> 1;
        }
        //翻转2-m行
        for(int i = 2; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                if(b[i-1][j]) tranc(i,j);
            }
        }
        //判断这种翻转方式是否合法
        int j;
        for(j = 1; j <= n; j ++){
            if(b[m][j]) break;
        }
        if(j == n + 1 && fNum < aNum) record();
    }
    //不合法
    if(aNum == 10000){
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    //合法
    for(int i = 1; i <= m; i ++){
        cout << ans[i][1];
        for(int j = 2; j <= n; j ++){
            cout << " " << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注