3.26日总结

1.Fliptile

Sample Input

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Sample Output

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

题意：在题目输入的矩阵，在这个矩阵的基础上，通过最少基础反转，可以将矩阵元素全部变为0，如果不能达到目标则输出"IMPOSSIBLE"，达到目标则输出一个操作最少次数的矩阵。

思路：由于在同一个位置翻转两次的话，相当于没有翻转，所以每一个位置有且仅能最多翻转一次，想要将矩阵某个位置的1变为0，只能通过操作下一行同一列的位置，可以对第一行的元素按照要求翻转多次，次数为2^m(m为矩阵的列数)，直到所有的情况都尝试过。

下面是AC代码:

#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<vector>
using namespace std;int mp[20][20];
int ans[20][20];
int temp_ans[20][20];
int temp[20][20];
int n,m;
int mi=123456789;void fi(int x,int y)//翻转本身和相邻位置 
{temp[x][y]^=1;temp[x-1][y]^=1;temp[x+1][y]^=1;temp[x][y+1]^=1;temp[x][y-1]^=1;
}bool isok()
{for(int i=0;i<m;i++){if(temp[n-1][i]) return 0;}	return 1;//判断翻转是否合理 
}void solve()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>mp[i][j];}}int k=(1<<m);int count=0;while(k--){memset(temp_ans,0,sizeof(temp_ans));memcpy(temp,mp,sizeof(mp));int cnt=0;int dy=0;while((1<<dy)<=count){if((1<<dy)&count){cnt++; temp_ans[0][dy]=1;//多次不同情况翻转第一行 fi(0,dy);}dy++;}count++;for(int i=0;i<n-1;i++){for(int j=0;j<m;j++){if(temp[i][j]){temp_ans[i+1][j]=1;//记录翻转位置 fi(i+1,j);//翻转下一个位置 cnt++;//记录翻转次数 }}}if(cnt<mi&&isok())//判断 {mi=cnt;//更新最优解 memcpy(ans,temp_ans,sizeof(temp_ans));}}if(mi>1234567)//代表没找到合理解 {cout<<"IMPOSSIBLE\n";}else//输出优解答案 {for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<ans[i][j]<<" ";}cout<<"\n";}}
}
int main()
{int t;t=1;while(t--){solve();}return 0;
}