欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

POJ-3279 枚举+dfs

程序员文章站 2022-03-03 08:06:23
由于上一行的状态决定了下一行的翻转,所以只需要枚举第一行的翻转情况 (用二进制状态下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]; //最终结果sta...

由于上一行的状态决定了下一行的翻转,所以只需要枚举第一行的翻转情况 (用二进制状态下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

相关标签: 搜索