- #include
- #include
- using namespace std;
- const intdx[5]= {-1,0,0,0,1};
- const intdy[5]= {0,-1,0,1,0};
- int M,N;
- inttile[16][16];//起始
- intopt[16][16];//保存最优解
- intflip[16][16];//保存中间结果
- //查询(x,y)的颜色
- int get(intx,int y)
- {
- intc=tile[x][y];
- for(inti=0; i<5; i++)
- {
- intx2=x+dx[i];
- inty2=y+dy[i];
- if(x2>=0&&y2>=0&&x2N)
- {
- c+=flip[x2][y2];
- }
- }
- returnc%2;
- }
- //求出第一行确定情况下的最小操作次数
- //不存在解的话返回-1
- int calc()
- {
- //求出从第二行开始的翻转方法
- for(inti=1; i)
- {
- for(intj=0; j)
- {
- if(get(i-1,j)!=0)
- {
- //(i-1,j)是黑色的话 必须翻转这个格子flip[i][j]=1;
- }
- }
- }
- //判断最后一行是否全白
- for(intj=0; j)
- {
- if(get(M-1,j)!=0)
- {
- return-1;//无解
- }
- }
- //统计翻转的次数
- intres=0;
- for(inti=0; i)
- {
- for(intj=0; j)
- {
- res+=flip[i][j];
- }
- }
- return res;
- }
- int main()
- {
- cin>>M>>N;
- for(inti=0; i)
- {
- for(intj=0; j)
- {
- cin>>tile[i][j];
- }
- }
- intres=-1;
- //按照字典序尝试第一行的所有可能性
- for(inti=0; i<1<)
- {
- memset(flip,0,sizeof(flip));
- for(intj=0; j)
- {
- flip[0][N-j-1]=i>>j&1;
- }
- intnum=calc();
- if(num>=0&&(res<0||res>num))
- {
- res=num;
- memcpy(opt,flip,sizeof(flip));
- }
- }
- if(res<0)
- {
- //无解cout<<"IMPOSSIBLE"<<endl;
- }
- else
- {
- for(inti=0; i)
- {
- for(intj=0; j)
- {
- cout<" ";
- }
- cout<<endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1967001.html