原題在這里：原題鏈接
思路：這個圖形可以用一個數的二進制表示，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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272974.html
標籤：其他
上一篇：Linux的指令1 基本指令
下一篇：QFont::setPointSize: Point size <= 0, must be greater than 0