#假期蓝桥杯练习:

假期蓝桥杯练习

【题目】

如图【1.png】所示六角形中，填入1~12的数字。

使得每条直线上的数字之和都相同。

图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？

【1.png】

思路分析，首先将12个空看成数组，1-12依次填入。
这是我第一次学习dfs算法，利用dfs进行全排列扫描，凑出12个数字后进行6次加法比对，通过比对则输出，*号位为res[6]。
数组is[]用于判断1-12的数字是否被使用，判断失败在dfs中用is[i]=0；进行回溯。

代码实现如下:

package 蓝桥杯;

import java.util.ArrayList;


public class 六角填数 {
	private static int[] res=new int[13];
	private static int[] is=new int [13];
	
	public static void main(String[] args) {
		res[1]=1;   //结果集
		res[2]=8;
		res[12]=3;
		is[1]=1;    //1-12数被填入标为1
		is[8]=1;
		is[3]=1;
		dfs(1);   
	}
 
	private static void dfs(int x ) {
		if(x==1||x==2||x==12) {   //1,2,12填过
			dfs( x+1);
			return;
		}
		if(x==13) {        //res12个数填满时判断六条边相加
			checkall();
		}
		for(int i=1;i<13;i++) {
			if(is[i]==0) {   //填数
				is[i]=1;
				res[x]=i;
			//	System.out.println(res[1]+" "+res[2]+" "+res[3]+" "+res[4]+" "+res[5]+" "+res[6]+" "+res[7]+" "+res[8]+" "+res[9]+" "+res[10]+" "+res[11]+" "+res[12]);
				dfs(x+1); //填下个个数
				is[i]=0;   //不行清零回溯
			}
		}
	}
	private static void checkall() {
		int i;
		int a=res[1]+res[3]+res[6]+res[8];
		int b=res[1]+res[4]+res[7]+res[11];
		int c=res[8]+res[9]+res[10]+res[11];
		int d=res[2]+res[3]+res[4]+res[5];
		int e=res[2]+res[6]+res[9]+res[12];
		int f=res[5]+res[7]+res[10]+res[12];
		if(a==b&&a==c&&a==d&&a==e&&a==f) {
			System.out.println(res[6]);
				System.out.println(res[1]+" "+res[2]+" "+res[3]+" "+res[4]+" "+res[5]+" "+res[6]+" "+res[7]+" "+res[8]+" "+res[9]+" "+res[10]+" "+res[11]+" "+res[12]);
		}
		else {
			return;
		}
		
	}
 
}