今日学习记录
1. 3279 — Fliptile
关键词：枚举
问题分析：
经典踩格子游戏,每次踩一个格子,该格子和相邻格子会翻面,要求最优的翻面方案(翻的次数最少)
核心思路: 要最后的格子都为白面,我们每踩一次都会影响其他格子,首先我们先看一个简化版本的
- 假设我们把该格子放到一维的格子上,那么我们只按顺序枚举一次,我们无法处理枚举之前的数据,但我们可以处理之后的数据,所以考虑枚举右维护左,先把前面的格子都变为 0,后面的受到影响后面还可以再处理,最后只用检验最后的数是否为 0 就行,这样看其实翻面的次数和方案是固定的,因为第一个点决定了第二个点是否翻面,第二个点决定了第三个点是否翻面,这样就只有一种方案,所以关键点在于第一个点,但是你可能感觉第一个点是无关的,因为翻他似乎影响不了什么
- 看这个例子 1100000,如果只考虑从第二个开始的话最后有一个 1 消不掉,要对第一个位子进行翻转,可以看出我们其实也不知道在什么时候翻,所以枚举每种情况 所以将其推行到二维的表格上时就是一样的了,枚举第一行的所有情况,再根据上面的规则去遍历下面的数据,有点长
**最终代码：
#include <iostream>
#include <cstdlib>
#include <vector>
#include<algorithm>
#include<utility>
#include<cstring>
#include<climits>
using namespace std;
#define MEME(x,y) memset(x,y,sizeof(x))
int n,m;
int brr[16][16];//原模板
int arr[16][16];//动态模板
int ans[16][16];
int temp[16][16];//动态模板
void press(int i,int j){
if(i-1>=0) arr[i-1][j] ^= 1;
arr[i][j] ^= 1;
if(i+1<n) arr[i+1][j] ^= 1;
if(j-1>=0) arr[i][j-1] ^= 1;
if(j+1<m) arr[i][j+1] ^= 1;
}
int slove(){
int o = 0;
//先根据temp第一行来改变arr
for(int i = 0;i<m;i++){
if(temp[0][i]){
press(0,i);
o++;
}
}
//剩下的
for(int i = 1;i<n;i++){
for(int j = 0;j<m;j++){
if(arr[i-1][j]){
press(i,j);
temp[i][j] = 1;
o++;
}
}
}
//检查最后一行
for(int i = 0;i<m;i++){
if(arr[n-1][i]) return INT_MAX;
}
return o;
}
int main() {
cin>>n>>m;
int count = INT_MAX;
//输入
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
cin>>brr[i][j];
}
}
//开始遍历每种第一行的选择情况
for(int k = 0;k<(1<<m);k++){
//重置
MEME(temp,0);
//搞
for(int j = 0; j < m; j++) {
if(k & (1 << j)) {
temp[0][j] = 1;
}
}
//重置
memcpy(arr,brr,sizeof(brr));
//计数
int cnt = slove();
//比较答案
if(cnt<count){
count = cnt;
memcpy(ans,temp,sizeof(temp));
}
}
if(count==INT_MAX) cout<<"IMPOSSIBLE";
else {
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
cout<<ans[i][j];
if(j!=m-1) cout<<" ";
}
cout<<endl;
}
}
return 0;
}学到的点：
- 经典翻面小游戏