题意:有一个M*N的棋盘,每一个格子只有两种状态0或1,每次可以选择一个格子执行翻转操作,并且与该格子相邻的4个格子都会被翻转,求将所有格子都翻转成0所需要的最小操作数,若有多种方案,输出字典序最小的方案数。
思路:枚举第一行的状态,深搜接下来每行。此题由上往下搜,所以直接搜四个方向就可以,当前格子状态和周围四个+本身有关。每次记录翻转的最小步数,此题只要步数最小就可以AC。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <memory.h>
#define clc(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=;
const int inf=0x3f3f3f3f;
int n,m;
int a[][];
int flip[][];
int p[][];
int dir[][]={{,},{,-},{,},{-,}};
int ok(int x,int y){
int xx,yy;
int val=a[x][y];
for(int i=;i<;i++){
xx=x+dir[i][];
yy=y+dir[i][];
if(xx>=&&xx<=m-&&yy>=&&yy<=n-){
val+=flip[xx][yy];
}
}
return val&;
} int dfs(int k){
int sum,i,j;
if(k==m-){
for(i=;i<n;i++){
if(ok(k,i))
break;
}
if(i!=n)
return -;
sum=;
for(i=;i<m;i++){
for(int j=;j<n;j++)
if(flip[i][j])
sum++;
}
return sum;
}
for(j=;j<n;j++){
if(ok(k,j))
flip[k+][j]=;
}
dfs(k+);
}
void work(){
int N=<<n,tem,num;
int ret=inf;
for(int i=;i<N;i++){
clc(flip,);
for(int j=n-,tem=i;j>=;j--,tem>>=){
flip[][j]=tem&;
}
num=dfs();
if(num!=-&&num<ret){
ret=num;
memcpy(p,flip,sizeof(flip));
}
}
if(ret==inf)
printf("IMPOSSIBLE\n");
else{
for(int i=;i<m;i++){
for(int j=;j<n;j++){
if(j==)
printf("%d", p[i][j]);
else
printf(" %d",p[i][j]);
if(j==n-)
printf("\n");
}
}
}
}
int main(){
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&m,&n)){
for(int i=;i<m;i++){
for(int j=;j<n;j++){
scanf("%d",&a[i][j]);
}
}
work();
}
return ;
}