POJ3279反转(位运算)

2018-02-03 10:20:37来源:网络收集作者:管理员人点击

分享

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


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


#include
#include
#include
#include
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< 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;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台