首页 » C++ » POJ3279反转(位运算)

POJ3279反转(位运算)

原文 http://blog.csdn.net/Link_Ray/article/details/79219830

2018-02-01 02:00:55阅读(516)

题意:要用最少的步骤将题目所给的矩阵中的所有1都变为0,已知每次反转一个点时,其周围与其有公共边的格子都会反转。

做法:有条理的做,想要全部反转,首先要从局部开始,例如,先把第一行全部变为0,若第一行有n列,那么相应的对第一行的操作一共就有2^n种,每一种方法不一定都能将第一行全部置为0,更有可能没有一种方法将第一行置为0,假定随便选一种方法作用于第一行,因为反转一个点会使其上下左右都反转,若第一行仍有某个点为1,那么下一行与其对应着同一列的那个点就必须反转(不管其原来是1还是0),从而使得第一行全部变为0,这也从而得到了下一行的反转方案,依次类推,直到做完最后一行的方案。此时若最后一行还有1,则说明此种方案不可行,否则,则成功。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int m,n;
int cur[20];
int tmp[20];
int getBit(int x, int i){ // 获取第i列的值
    return (x>>(n-i-1))&1;
}
void flip(int& x,int i){ // 反转
    x = x^(1<<(n-i-1));
}
int main(){
    //freopen("/Users/user/Desktop/in.txt","r",stdin);
    scanf("%d %d", &m, &n);
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j){
            int num;
            scanf("%d", &num);
            if(num)
                cur[i] += 1<<(n-j-1); //二进制对应着一个整数
        }
    int ans[20]; //当前的方案
    int res[20];//最终的方案
    int mintc = 1<<30;
    bool flag = false; int tc = 0;
    for(int i = 0; i < (1<<n); ++i){ // 总共的方案数
        memcpy(tmp,cur,sizeof(cur));
        tc = 0; // 记录反转次数
        for(int j = 0; j < m; ++j){
            if(j == 0) ans[j] = i;
            else ans[j] = tmp[j-1]; //除了第一行的方案,其余各行的方案都与前一行的状态相同
            for(int k = 0; k < n; ++k){
                if(getBit(ans[j], k)){
                    tc++;
                    if(k) flip(tmp[j],k-1); // 反转左边的
                    flip(tmp[j],k);//反转当前的
                    if(k < n-1)
                        flip(tmp[j],k+1); // 反转右边的
                }
            }
            if(j < m-1)
                tmp[j+1] ^= ans[j];//同时反转下一行的
        }
        if(tmp[m-1] == 0){ // 若最后一行全为0
            flag = true;
            if(tc < mintc){
                mintc = tc; 
                memcpy(res,ans,sizeof(res));
            }
        }
    }
    if(flag)
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(!j) printf("%d", getBit(res[i],j));
                else printf(" %d", getBit(res[i],j));
            }   
            printf("\n");
        }
    else
        printf("IMPOSSIBLE\n");
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹