我要评论由于上一行的状态决定了下一行的翻转，所以只需要枚举第一行的翻转情况 （用二进制状态下1表示翻转），后面的行就能确定。
import java.util.Arrays;
import java.util.Scanner;
public class Main_POJ3279 {
static int n,m,step,tstep;
static int[][] a = new int[20][20];
static int[][] res = new int[20][20]; //最终结果
static int[][] tres = new int[20][20]; //枚举的某一个状态结果
static int[][] ta = new int[20][20];
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
a[i][j] = sc.nextInt();
}
}
step = 1000;
for(int k=0;k<(1<<n);k++) { //由于上一行的状态决定了下一行的翻转 所以只需要枚举第一行的翻转情况 二进制状态下1表示翻转
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
ta[i][j] = a[i][j];
}
}
if(ok(k)) {
step = tstep;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
res[i][j] = tres[i][j];
}
}
}
}
if(step!=1000) {
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}else {
System.out.println("IMPOSSIBLE");
}
}
public static boolean ok(int k) {
tstep = 0;
for(int i=0;i<m;i++) {
Arrays.fill(tres[i], 0);
}
for(int i=0;i<n;i++) { // 第一行的翻转情况
if((k&(1<<n-i-1))!=0) {
filp(0,i);
}
}
for(int i=1;i<m;i++) {
for(int j=0;j<n;j++) {
if(ta[i-1][j] == 1) {
filp(i,j);
}
if(tstep>=step) return false; //保证字典序最小
}
}
for(int i=0;i<n;i++) { //检验最后一行是否都为0
if(ta[m-1][i] == 1)
return false;
}
return true;
}
public static void filp(int x,int y) {
tstep++;
tres[x][y] = 1;
ta[x][y] = 1-ta[x][y];
for(int i=0;i<4;i++) {
int xi = x+dx[i];
int yi = y+dy[i];
if(xi>=0&&xi<m&&yi>=0&&yi<n) {
ta[xi][yi] = 1-ta[xi][yi];
}
}
}
}
本文地址：https://blog.csdn.net/weixin_45948204/article/details/107696353
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
![Java List集合返回值去掉中括号(''[ ]'')的操作](http://www.lhsxpumps.com/_images5/10qianwan/20200829/s_0_202008290320291229.jpg)
网友评论