POJ 3279

• 点击的数组的字典序是一行一行看成字符串的(开头的0不要,从1开始)。
• 输出字典序的前提是step 相同,那么枚举点的操作是从0开始$ (000001)_2 $,字典序是1 , $ (11111)_2 $字典序是11111,所以我们已经默认的是按字典序枚举的,

  #include <iostream>
  #include <string.h>
  
  using namespace std;
  const int maxn = 16;
  
  int backup[maxn][maxn];
  int ch[maxn][maxn];
  int cp[maxn][maxn];
  int ans[maxn][maxn];
  int next1[5][2] = {0,0,0,1,1,0,0,-1,-1,0};
  int n,m;
  bool flag = true;
  
  void click(int x,int y) {
  	for (int i=0; i<5; i++) {
  		int tx = x + next1[i][0];
  		int ty = y + next1[i][1];
  		if (tx>=1 && tx<=n && ty>=1 && ty<=m) ch[tx][ty] ^= 1;
  	}
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> n >> m;
  	for (int i=1; i<=n; i++)
  		for (int j=1; j<=m; j++) 
  			cin >> ch[i][j];
  	memcpy(backup,ch,sizeof ch); // 原数组备份
  
  	int anstep = 0x3f3f3f3f;
  	for (int states=0; states < (1<<m); states++) {
  		int step = 0;
  		memset(cp,0,sizeof cp);
  
  		for (int j=m-1; j>=0; j--) 
  			if ( (states >> j) & 1 ) {
  				click(1,m-j);
  				cp[1][m-j] = 1;
  				step++;
  			}
  		// 从第二行开始每一行看上一行的值
  		for (int i=2; i<=n; i++) {
  			for (int j=1; j<=m; j++) {
  				if (ch[i-1][j] == 1) { // 黑是1,让他变0(白)
  					step++;
  					click(i,j);
  					cp[i][j] = 1;
  				}
  			}
  		}	
  		int j = 1; 
  		for (; j<=m; j++) 
  			if (ch[n][j] == 1) break;
  		if (j == m+1 && step < anstep) {
  			flag = false;
  			anstep = step;
  			memset(ans,0,sizeof ans); // 要更新ans的值了
  			memcpy(ans,cp,sizeof cp);
  		}
  		memcpy(ch,backup,sizeof backup);
  	}
  	if (flag) printf("IMPOSSIBLE\n");
  	else {
  		for (int i=1; i<=n; i++) {
  			for (int j=1; j<=m; j++) {
  				printf("%d",ans[i][j]);
  				if (j != m) printf(" ");
  			}
  			printf("\n");
  		}
  	}
  	return 0;
  }