poj 1222 熄灯问题
–第二次按下同一个按钮时，将抵消第一次按下所产生的效果。
–每个按钮最多只需按一次。
–每个按钮按下的顺序对最后的结果没有影响。
–对第一行每个点亮的灯，只需按下第二行相应的灯，就可以熄
灭第一行所有的灯，那么如此重复下去，第1,2,3,4行的灯都可以熄灭。
位运算解法
//熄灯问题 #include <iostream> #include <cstring> using namespace std; char old[10], lights[10], result[10]; //原数组，灯数组，结果数组 void SetBit(char &c, int i, int v) //c代表第i行的字符，把第i行的第j位设置成v { if(v) { c = c | (1 << i); } else c = c & ~(1 << i); } //v = 1 //如果把第3位上的设置为1 //0010 0101 //0010 0101 | 0000 1000 = 0010 1101 按位或运算 //v = 0 //如果把第2位上的位设置为0 //0010 0101 //~（1 << 2）= ~(0000 0100) = (1111 1011) //0010 0101 & 1111 1011 = 0010 0001 int GetBit(char c, int i) //取出c的第i位上的数字 { return (c >> i) & 1; } //0010 0001 右移3位 0000 0100 & 0000 0001 = 0 void FilpBit(char &c, int i) //翻转c的第i位 { c = c ^ (1 << i); } //0010 0101 //翻转第3位上的数字 //0010 0101 ^ 0000 1000 = 0010 1101 void OutPutResult() { for(int i = 0; i < 5; ++i) for(int j = 0; j < 6; ++j) { cout << GetBit(result[i], j); if(j < 5) cout << " "; else cout << endl; } } int main() { int kase; cin>>kase; for(int i = 1;i <= kase ;i++) { int v, switchs; for(int i = 0; i < 5; ++i) for(int j = 0; j < 6; ++j) { cin >> v; SetBit(old[i], j, v); } for(int n = 0; n < 1 << 6; ++n) { //6个开关，2的6次方种情况， (1 << 6 == 2^6) memcpy(lights, old, sizeof(old)); //还原lights数组 switchs = n; for(int i = 0; i < 5; ++i) { result[i] = switchs; // 0 0 1 0 1 0 for(int j = 0; j < 6; ++j) { if(GetBit(switchs, j)) { if(j > 0) FilpBit(lights[i], j - 1); //翻转左边 FilpBit(lights[i], j); //翻转本身 if(j < 5) FilpBit(lights[i], j + 1); //翻转右边 } } if(i < 4) lights[i + 1] ^= switchs; switchs = lights[i]; } if(lights[4] == 0) { printf("PUZZLE #%d\n",i); OutPutResult(); break; } } } return 0; }
局部替代整体
借鉴某位大佬的 博客
#include<stdio.h> int puzzle[6][8],press[6][8]; bool guess(){ int c,r; for(r=1;r<5;++r){ for(c=1;c<7;++c){ press[r+1][c]=(puzzle[r][c]+press[r][c-1]+press[r][c]+press[r][c+1]+press[r-1][c])%2; }//根据press第一行和puzzle数组计算press的其他值 } for(c=1;c<7;++c){ if((press[5][c-1]+press[5][c]+press[5][c+1]+press[4][c])%2!=puzzle[5][c]) return false; }// return true; } void zhenghe(){//将数据进行整合 int c; bool success; for(c=1;c<7;c++){ press[1][c]=0; } while(guess()==false){//当没有正确答案时，继续下去。找到正确的答案为止 press[1][1]++; c=1; while(press[1][c]>1){ press[1][c]=0; c++; press[1][c]++;//模拟二进制，六位二进制 } } return; } int main(){ int n,i,r,c,a=1; scanf("%d",&n); for(r=0;r<6;++r){ press[r][0]=0; press[r][7]=0; } for(c=1;c<7;++c){ press[0][c]=0; } for(i=0;i<n;++i){ for(r=1;r<6;++r){ for(c=1;c<7;++c){ scanf("%d",&puzzle[r][c]);//输入 } } zhenghe(); printf("PUZZLE #%d\n",a);a++; for(r=1;r<6;++r){ for(c=1;c<7;++c){ printf("%d ",press[r][c]);//输出 } printf("\n"); } } return 0; }
飞行员兄弟 4*4
#include <cstdio> using namespace std; char s[4]; int mp[4][4]; int main() { int arr=0; for(int i=0;i<4; i++) { scanf("%s",s); for(int j=0; j<4; j++) { if(s[j] == '+') { for(int k=0; k<4; k++) { mp[i][k] ++; mp[k][j] ++; } mp[i][j] --; } } } for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { if(mp[i][j] % 2 == 1) arr ++; } } printf("%d\n",arr); for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { if(mp[i][j] % 2 == 1) printf("%d %d\n",i + 1, j + 1); } } return 0; }
翻棋子游戏 poj 1753
#include<cstdio> #include<iostream> #include<cstring> using namespace std; struct node { int x; //用十进制的整数的后16位表示该节点的状态 int steps; //记录到达该节点的步数 int i; //是翻动哪个棋子到达当前的状态，避免返回以前的状态 }; bool vis[100000]={false}; char str[10]; node queue[100000]; void flip(int i,node a,node &b) //i=当前要翻动的棋子编号(0-15),a为queue[p]的形参，b为queue[q]的引用 { int r=i/4,c=i%4; //r、c为当前的要翻动的第i个棋子的行和列坐标 b.x=a.x; //为了不改变前一次记录的状态，先拷贝给b。再来翻棋子，记录新状态。 b.x=b.x^(0x1<<i); //用^0x1取反(0x1表示16进制的1) if(r>0) b.x=b.x^(0x1<<(i-4)); //翻i对应位置上面的棋子 if(r<3) b.x=b.x^(0x1<<(i+4)); //翻i对应位置下面的棋子 if(c>0) b.x=b.x^(0x1<<(i-1)); //翻i对应位置左边的棋子 if(c<3) b.x=b.x^(0x1<<(i+1)); //翻i对应位置右边的棋子 b.i=i; b.steps=a.steps+1; } void init() { queue[0].x=0; //初始化为16进制的0 (10进制和16进制的0是一样的) queue[0].steps=0; queue[0].i=-1; for(int i=0;i<4;i++) { scanf("%s",str); for(int j=0;j<4;j++) { if(str[j]=='b') //黑棋对应的位置置1 (用|0x1置1) queue[0].x=(queue[0].x|(0x1<<i*4+j)); } } } void bfs() { int p=0,q=0; while(!(queue[q].x==0||queue[q].x==0xffff)) //如果不满足全0或者全1的状态 { for(int i=0;i<16;i++) { if(queue[p].i==i) continue; q++; //尾指针后移，为新状态开辟新的记录空间 flip(i,queue[p],queue[q]); if(vis[queue[q].x]) q--; vis[queue[q].x]=true; if(queue[q].x==0||queue[q].x==0xffff) break; } if(p==q) { printf("Impossible\n"); break; } p++; //头指针后移1位，将当前状态作为搜索的初始状态 } if(queue[q].x==0||queue[q].x==0xffff) printf("%d",queue[q].steps); } int main() { init(); bfs(); return 0; }
