1815:画家问题 (dfs java)

题目链接


和熄灯问题很像。如果暴力搜索的话，棋盘大小15*15，每个位置的状态有两个变或者不变，那么将有$2^{15\ast 15}$个状态，显然不能直接搜。事实上，我们可以枚举第一行的状态，因为第一行的状态一旦确定，剩余行也随之确定，这是因为对于与第一行的w，只能是第二行的这个位置修改才能使得第一行的‘w’变为’y’,其他行的修改不会影响到第一行，同理，第二行确定后，只能由第三行改变第二行为‘w’的位置。最后只需要检查最后一行是否都为‘y’即可。
所以枚举第一行的状态就只有$2^{16}$个状态了。
需要注意的是，要及时恢复棋盘原来的状态，这一点在枚举第一行状态的时候很容易想到，但是当枚举完第一行状态进行check是否是可行的方案时，需要重新建立一个棋盘的副本去检查，因为检查的过程也涉及到颜色的改变，检查完毕之后接着dfs应该用的是原来的棋盘。

import java.util.*;public class Main{public static char[][] G=new char[16][16];public static int[] dx= {0,0,-1,1};public static int[] dy= {-1,1,0,0};public static int ans=0x3f3f3f3f;public static Map<Character,Character> mp=new HashMap<Character,Character>();public static void change(int x,int y,int n,char[][] g) {//改变(x,y)及上下左右的颜色//change两次就相当于没有changeg[x][y]=mp.get(g[x][y]);for(int i=0;i<4;i++) {int newx=x+dx[i];int newy=y+dy[i];if(newx<0 || newx>=n || newy<0 || newy>=n) {continue;}g[newx][newy]=mp.get(g[newx][newy]);}}public static int check(char[][]tmpG,int n) {//根据第一行的状态改变剩余行的状态int cnt=0;for(int i=1;i<n;i++) {for(int j=0;j<n;j++) {if(tmpG[i-1][j]=='w') {cnt++;change(i,j,n,tmpG);}}}for(int j=0;j<n;j++) {if(tmpG[n-1][j]=='w') {return 0x3f3f3f3f;}}return cnt;}public static void dfs(int pos,int n,int CNT) {//当前位置pos有两种状态，改/不改if(pos==n) {//第一行的状态枚举完毕，检查是否都变为黄色char[][] tmpG=new char[16][16];for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {tmpG[i][j]=G[i][j];}}ans=Math.min(check(tmpG,n)+CNT,ans);return;//递归终止之后记得返回，否则还会执行后面}change(0,pos,n,G);//改dfs(pos+1,n,CNT+1);change(0,pos,n,G);//撤销改，即不改dfs(pos+1,n,CNT);}public static void main(String[] Args) {mp.put('w', 'y');mp.put('y', 'w');Scanner sc=new Scanner(System.in);int n;n=sc.nextInt();sc.nextLine();//吸收enterfor(int i=0;i<n;i++) {String tmp;tmp=sc.nextLine();for(int j=0;j<n;j++) {G[i][j]=tmp.charAt(j);}}//枚举第一行的状态，每个位置可以变或者不变//第一行状态选定后，其他行的状态就随之确定了dfs(0,n,0);if(ans==0x3f3f3f3f) {System.out.print("inf");}else {System.out.print(ans);}
//		for(int i=0;i<n;i++) {
//			for(int j=0;j<n;j++) {
//				System.out.print(G[i][j]+" ");
//			}
//			System.out.println();
//		}}
}