Fliptile（枚举&DFS）

Fliptile

题目传送门

Fliptile

题目大意

给你一个$n\times m$的矩阵，矩阵由0和1组成，可以选择一个点翻转 翻转：将该点以及该点上下左右的点翻转（0变1,1变0） 求将矩阵翻转成全为0的最小步数，若没有则输出“IMPOSSIBLE”

思路

很经典的题目了，可以从第二行开始推，用第二行的翻转将第一行全变成0，同理，第三行变第二行为全0… 到最后一行时，判断该行是否为0，全为0即为这种方法可以。

对于第一行的状态可以直接枚举，枚举第一行翻转的情况（采取二进制的枚举方式），对于每次枚举的答案取最小即可

AC Code

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f #define int long long // #define TDS_ACM_LOCAL const int N=20; int ans; int mp[N][N], s[N][N], tmp[N][N]; int dirx[]={0,1,0,-1,0}; int diry[]={0,0,1,0,-1}; int n, m; bool check(int x, int y){ //求得（x，y）的颜色 int temp=mp[x][y]; for(int i=0; i<5; i++){ int xx=x+dirx[i]; int yy=y+diry[i]; if(xx>=1 && xx<=n && yy>=1 && yy<=m) temp+=tmp[xx][yy]; } return temp&1; } int dfs(){ for(int i=2; i<=n; i++) for(int j=1; j<=m; j++) if(check(i-1,j)) //上一行为黑色的地方翻转 tmp[i][j]=1; for(int i=1; i<=m; i++) //最后一行如果有黑色的就返回，该情况无效 if(check(n,i)) return INF; int temp=0; for(int i=1; i<=n; i++) //计算当前枚举的情况的翻转次数 for(int j=1; j<=m; j++) temp+=tmp[i][j]; return temp; } void solve(){ ans=INF; cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>mp[i][j]; for(int i=0; i<(1<<m); i++){ //枚举第一行的所有翻转的状态 memset(tmp, 0,sizeof(tmp)); for(int j=1; j<=m; j++) tmp[1][m-j+1]=(i>>(j-1)) &1; //求得当前第一行的状态 int cnt=dfs(); if(cnt<ans){ //该解目前最优 ans=cnt; memcpy(s, tmp, sizeof(tmp)); //将枚举的二维数组复制到答案中保存 } } if(ans==INF) {cout<<"IMPOSSIBLE"<<endl; return ;} for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++) cout<<s[i][j]<<" "; cout<<endl; } return ; } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef TDS_ACM_LOCAL freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin); freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout); #endif solve(); return 0; }