本文主要是介绍牛客——牛可乐的翻转游戏（状压，dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
牛可乐发明了一种新型的翻转游戏！
在一个有 nnn 行 mmm 列的棋盘上，每个格子摆放有一枚棋子，每一枚棋子的颜色要么是黑色，要么是白色。每次操作牛可乐可以选择一枚棋子，将它的颜色翻转（黑变白，白变黑），同时将这枚棋子上下左右相邻的四枚棋子的颜色翻转（如果对应位置有棋子的话）。
牛可乐想请你帮他判断一下，能否通过多次操作将所有棋子都变成黑色或者白色？如果可以，最小操作次数又是多少呢？
输入描述:
第一行两个整数 n,m(1≤n≤100,1≤m≤10)n,m(1\leq n\leq 100,1\leq m\leq 10)n,m(1≤n≤100,1≤m≤10)，代表棋盘的行数和列数。之后 nnn 行，每行 mmm 个数字，第 iii 个数字如果为 000 ，代表对应位置的棋子为白色，如果为 111 则为黑色。
输出描述:
如果无法将所有棋子变成一个颜色，输出 "Impossible"(不含引号)，否则输出变成一个颜色的最小操作次数。
#include<bits/stdc++.h>
using namespace std;int n, m;
string c[120], d[120];void overturn(int x, int y) {int dx[6] = {0, 0, 0, 0, 1, -1};int dy[6] = {0, 0, 1, -1, 0, 0};for (int i = 1; i <= 5; i++) {int a = x + dx[i];int b = y + dy[i];if (a >= 0 && b >= 0 ) {d[a][b] = (d[a][b] == '0' ? '1' : '0');}}
}int recurrence(int state, char target) {int step = 0;for (int i = 0; i < n; i++) {d[i] = c[i];}for (int i = 0; i < m; i++) {if (state & (1 << i)) {step++;overturn(0, i);}}for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {if (d[i-1][j] != target) {step++;overturn(i, j);}}}for (int i = 0; i < m; i++) {if (d[n-1][i] != target) {return 1000;}}return step;
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> c[i];}int ans = 1000;for (int i = 0; i < (1 << m); i++) {ans = min(ans, recurrence(i, '0'));ans = min(ans, recurrence(i, '1'));}if (ans == 1000) {cout << "Impossible";} else {cout << ans;}return 0;
}#include<iostream>
using namespace std;
const int N=105,M=1200;
int a1[N],a2[N],cnt[M],n,m;void Init(){for(int i=0;i<M;++i){for(int j=0;j<m;++j){if(i&(1<<j)) ++cnt[i];}}
}int dfs(int pre,int op,int *a){int res=0;for(int i=1;i<n;++i){res+=cnt[pre];int cur=( (pre^(pre<<1)^(pre>>1)^op)&( (1<<m)-1) )^a[i];op=pre; pre=cur;}if(pre==0) return res;else return 1e9;}int main(){char num;cin>>n>>m;Init();for(int i=0;i<n;++i){for(int j=1;j<=m;++j){cin>>num;if(num=='1') a1[i]|=1<<(m-j);else a2[i]|=1<<(m-j);}}//for(int i=0;i<n;++i) cout<<a1[i]<<" "<<a2[i]<<endl;int res=1e9;for(int i=0;i<(1<<m);++i){res=min(res,cnt[i]+dfs(( (i^(i<<1)^(i>>1))&( (1<<m)-1) )^a1[0] ,i,a1));res=min(res,cnt[i]+dfs(( (i^(i<<1)^(i>>1))&( (1<<m)-1) )^a2[0] ,i,a2));}if(res==1e9) cout<<"Impossible";else cout<<res;return 0;
}
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int change[120];
int map[120];
int m,n;
int wei(int num){int sum=0;while(num){sum++;num&=num-1;}return sum;
}
int wei(int a[]){int step=0x3f3f3f;for(change[0]=0;change[0]<(1<<m);change[0]++){map[0]=a[0];int sum=0;for(int j=0;j<n;j++){sum+=wei(change[j]);map[j]=map[j]^change[j]^((change[j]<<1)&((1<<m)-1))^(change[j]>>1);map[j+1]=a[j+1]^change[j];change[j+1]=map[j];}if(!map[n-1])step=min(sum,step);}return step;
}
int main() {int a[120];int b[120];memset(a,0,sizeof(a));memset(b,0,sizeof(b));cin>>n>>m;char d;getchar(); for(int i=0;i<n;i++){for(int j=0;j<m;j++){d=getchar();d=='0'?a[i]=a[i]|(1<<j):b[i]=b[i]|(1<<j);}getchar();}int ans=0x3f3f3f;ans=min(wei(a),wei(b));if(ans>m*n)cout<<"Impossible"<<endl;else cout<<ans<<endl;return 0;
}这种题好难理解呀，搜了好多题解，感觉懂了，但是再遇到也不一定会写，所以这种题还是先放一放吧。
补充：
状压是一种常用于位运算的技巧，用于表示和处理集合等离散对象的状态。它通过使用整数的二进制位来表示对象或状态的某些特征，以达到节省空间和提高效率的目的。
在状压中，通常使用整数的二进制位来表示某个集合的状态，其中每一位可以表示集合中的某个元素是否存在或某个状态是否满足某种条件。例如，对于一个大小为n的集合，可以使用一个n位的整数来表示集合的状态，其中每一位表示集合中对应元素的存在与否。
状压常用于解决组合数学、动态规划、图论等问题，特别是当集合的大小较小且需要频繁判断和操作集合的状态时，状压可以显著提高算法的效率和减少空间复杂度。
使用状压技巧需要熟悉位运算的基本操作，例如与（&）、或（|）、异或（^）等，以及位移操作（<<、>>）等。同时，也需要注意处理位运算可能导致的溢出和边界情况。
这篇关于牛客——牛可乐的翻转游戏（状压，dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
