题目描述
本来想搞bfs或者dfs的,结果暴力枚举就好了。
由于确定第一行的翻转情况之后,后面的翻转情况都可以被预知。所以按字典序枚举第一行的翻转情况,求出所有元素的翻转情况之后再检查翻转后是否完成全0,比较记录最佳ans即可。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
int dx[] = {0, 0, 0, -1, 1};
int dy[] = {0, 1, -1, 0, 0};
int g[N][N];
int n, m;
int s[N][N], ans[N][N];//记录每一次翻转位置的地图和最佳翻转地图
int check()
{
int gg[N][N];//每一次操作的地图
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
gg[i][j] = g[i][j];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(i != 1 && gg[i - 1][j] == 1) //如果该元素正上方的元素是1,
s[i][j] = 1;//则该元素需要翻转
if(s[i][j])//如果翻转
{
for(int k = 0; k < 5; k++)//将自己和上下左右翻转
{
int xx = i + dx[k];
int yy = j + dy[k];
gg[xx][yy] = 1 - gg[xx][yy];
}
}
}
}
int res = 0;//记录翻转次数
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
res += s[i][j];
if(gg[i][j]) return -1;//检查是否全0
}
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
int ansmin = 0x3f3f3f3f;//ansmin初始化为无限
for(int k = 0; k < (1 << m); k++)//枚举0到2^m-1的二进制数作为第一行
{
memset(s, 0, sizeof s);
for(int i = 0; i < m; i++)
if(k & (1 << i)) s[1][m - i] = 1;
int a = check();
if(a != -1 && a < ansmin)//如果出现更优解,更新ans
{
ansmin = a;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans[i][j] = s[i][j];
}
}
if(ansmin != 0x3f3f3f3f)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
else
puts("IMPOSSIBLE");
return 0;
}
白书吗? 哈哈我之前也在刷这本书
啊白书是啥,我刷的kuangbin题集😰
哦 我以为是 挑战程序设计竞赛(第2版) 第二章习题
那没事了,我都不买书的。众所周知,acmer买书除了字典从来不看🙏