最近在刷kuangbin神犇的各种套题。。。。感觉自己好弱啊。。。。。还是要多多训练，跟上大神的脚步。最近的这十几题都比较水，记下来这一条我比较印象深刻、也比较难的题目吧（之后应该不会再有水题写了，珍惜水题啊QAQ）
思考
题目其实很简单，踩黑白啊，而且规模也不算大。问题在于我们怎么穷举。注意到一个问题，我们对单行中先后变换的次序其实不改变最后的结果。也就是说，对于单列的变换，其实我们可以纯粹的只考虑上下带来的影响。而又注意到每行实际上只影响上下单行，所以我们可以规定一个处理的方向（如从上而下），那么我们每次只需要考虑最新的一行对上面一行带来的影响了。需要注意的是，这种思想我们之后估计会经常用到。（不过本菜狗估计还是做不对emmmmm
这题就是这个思路。穷举第一行的踩踏方式，那么会产生有黑有白。对上一行的黑，只能有此列的下一行来处理，因此我们逐行处理就行了。最后看最后一行合不合法即可。保存最小数据。
代码
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
int maze[18][18],step[18][18];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
int m,n;
int judge(int val)
{
int tmpmaze[18][18];
memcpy(tmpmaze,maze,sizeof(maze));
int cnt=0;
memset(step,0,sizeof(step));
for(int i=1;i<=m;++i)
{
if(i==1) for(int j=1;j<=n;++j)
{
if((val>>(n-j))&1)
{
step[i][j]++;cnt++;
for(int k=0;k!=5;++k)
{
int tx=i+dx[k],ty=j+dy[k];
if(tx>=1 && tx<=m && ty>=1 && ty<=n)
tmpmaze[tx][ty]^=1;
}
}
}
else for(int j=n;j>=1;--j)
{
if(tmpmaze[i-1][j])
{
step[i][j]++;cnt++;
for(int k=0;k!=5;++k)
{
int tx=i+dx[k],ty=j+dy[k];
if(tx>=1 && tx<=m && ty>=1 && ty<=n)
tmpmaze[tx][ty]^=1;
}
}
}
}
for(int i=1;i<=n;++i) if(tmpmaze[m][i]) return -1;
return cnt;
}
int main()
{
while(cin>>m>>n)
{
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
cin>>maze[i][j];
int minans=0x3f3f3f3f,minstep[18][18];
memset(minstep,0,sizeof(minstep));
for(int i=0;i!=(1<<n);++i)
{
int ans=judge(i);
if(ans!=-1 && minans>ans)
{
memcpy(minstep,step,sizeof(step));
minans=ans;
}
}
if(minans==0x3f3f3f3f)
cout<<"IMPOSSIBLE"<<endl;
else for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
cout<<minstep[i][j]<<" ";
cout<<endl;
}
}
return 0;
}