[蓝桥杯2017初赛]方格分割

原题在这里：原题链接

????思路：这个图形可以用一个数的二进制表示，0代表浅色，1代表深色，题目中说两部分的形状完全相等，则说明这两部分是关于中心对称的，也就是一个位置的对称位置与原位置的颜色不同。

剩下的就是用DFS查找有多少个相同颜色联通且面积为18的图形了，在这个操作中要定义一个vis数组，用来记录一个位置是否已经走过(防止死循环)且vis数组不能写在DFS里边(因为递归调用会重新定义这个数组，可以在main中，每一次赋值i就更新一次vis数组)；注意结果，因为题目说旋转对称的属于同一种分割法，正方形有四种旋转方式，所以结果要/4。

public class Main {
	public static int[][] map = new int[6][6];
	public static boolean vis[][];
//check函数用来检查联通的相同颜色的个数，如果=18，则说明此分割成立
	public static int check(int x,int y) {
//用sum记录相同颜色并且联通的色块
		int sum = 1;
//设立一个vis数组记录当前位置是否走过，防止出现死循环
		if(x+1<6&&!vis[x+1][y]&&map[x][y]==map[x+1][y]) {
			vis[x+1][y]=true;//符合条件的话则说明这个位置走过了
			sum+=check(x+1,y);//如果右边有，接着往右走，相同颜色的色块+1
		}
		if(x-1>=0&&!vis[x-1][y]&&map[x][y]==map[x-1][y]) {
			vis[x-1][y]=true;//符合条件的话则说明这个位置走过了
			sum+=check(x-1,y);//相同颜色的色块+1
		}
		if(y+1<6&&!vis[x][y+1]&&map[x][y]==map[x][y+1]) {
			vis[x][y+1]=true;//符合条件的话则说明这个位置走过了
			sum+=check(x,y+1);//相同颜色的色块+1
		}
		if(y-1>=0&&!vis[x][y-1]&&map[x][y]==map[x][y-1]) {
			vis[x][y-1]=true;//符合条件的话则说明这个位置走过了
			sum+=check(x,y-1);//相同颜色的色块+1
		}
		return sum;
	}
	public static void main(String[] args) {
//用一个数的二进制表示分布，0代表浅色，1代表深色
//如果形状相同，则说明图形中心对称，也就是对称点肯定是不一样的颜色；所以枚举2^18即可
		int ans = 0;
		for(int i=0;i<Math.pow(2,18);i++) {
			int temp = i;//对i进行操作，但不能改变数值，所以用temp代替
			for(int j=0;j<6;j++) {//6列
				for(int k=0;k<3;k++) {//3行
					map[j][k]=temp%2;
					map[6-j-1][6-k-1]=1-temp%2;//对称位置赋值
					temp/=2;//对下一个方格赋值
				}
			}
			vis = new boolean[6][6];
			vis[0][0]=true;
			if(check(0,0)==18) {
				ans++;
			}
		}
//之所以除以4，旋转后的图形算是一种，正方形有四种旋转方式
		System.out.println(ans/4);
	}
}