第七届蓝桥杯 省赛 JavaB组 方格填数

方格填数 如下的10个格子 （如果显示有问题，也可以参看【图1.jpg】） 填入0~9的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻） 一共有多少种可能的填数方案？ 请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：1580

思路：

package com.test.zx; public class Main { public static int count = 0 ; //记录方案数 public static boolean isVisit[] = new boolean[10] ; //判断一个数是否被访问过 public static int a[][] = new int[3][4] ; //填入方格里的数 public static void main(String args[]){ for(int i = 0 ; i < 3 ; i ++){ //初始化数据，（除了-1到10之间）的数都可行，这里初始化为-2 for(int j = 0 ; j < 4 ; j++){ a[i][j] = -2 ; } } for(int num = 0 ; num < 10 ; num++){//初始化所有数字均未填入 isVisit[num] = false ; } find(0,1) ; System.out.println(count); } private static void find(int i, int j) { if(i == 2&&j==3){ //判断是否填入最后一个格子，若是的则方案数+1 count++ ; } for(int num = 0 ; num < 10 ;num++){ //将0到9都填入该方格，看是否可行 if(judge(num,i,j)&&!(isVisit[num])){ //若可行 a[i][j] = num ; //将该数填入方格 isVisit[num] = true ; //并且将该数字设定为以访问 if(j==3){ //若查询到达列尾 find(i+1,0) ; //递归查询下一行 }else{ find(i,j+1) ; //递归查询下一列 } //重置该方格的状态，以便下一个数填入 a[i][j] = -2 ; isVisit[num] = false ; } } } private static boolean judge(int num, int i, int j) {//判断相邻格子的数字是否连续 if(i-1>=0 && (a[i-1][j] == num+1 || a[i-1][j] == num-1)){ //判断上方格子 return false ; } if(j-1>=0 && (a[i][j-1] == num+1 || a[i][j-1] == num -1)){ //判断左方格子 return false ; } if(i-1>=0 && j-1 >= 0 && (a[i-1][j-1] == num+1 || a[i-1][j-1] == num - 1)){ //判断左上方格子 return false ; } if(i-1>=0 && j+1 < 4 && (a[i-1][j+1] ==num+1 || a[i-1][j+1] == num - 1)){ //判断右上方格子 return false ; } if(j+1<4 && (a[i][j+1] == num+1 || a[i][j+1] == num-1)){ //判断右方格子 return false ; } if(i+1<3 && (a[i+1][j] == num+1 || a[i+1][j] == num-1)){ //判断下方格子 return false ; } if(i+1<3 && j-1>=0 && (a[i+1][j-1] == num+1 || a[i+1][j-1] == num-1)){ //判断左下方格子 return false ; } if(i-1<0 && j+1<4 && (a[i+1][j+1] == num+1 || a[i+1][j+1] == num-1)){ //判断右下方格子 return false ; } return true ; } }

public class Main{ static int count=0;//计数共有多少种情况 public static void main(String[]args){ int a[]=new int[12];//三行四列12个数 boolean visit[]=new boolean[10];//填入a[1]-a[10]共10个数 dfs(a,visit,1); System.out.println(count); } public static void dfs(int a[],boolean visit[],int num){ if(num==11){//10个数全部填入 if(judge(a)){ count++; } return; } for(a[num]=0;a[num]<10;a[num]++){//递归从a[1]开始填数 if(visit[a[num]]==false){ visit[a[num]]=true; num+=1; dfs(a, visit, num);//递归，填下一个数 num-=1; visit[a[num]]=false; } } } public static boolean judge(int a[]){ if ((a[1]==a[2]+1||a[1]==a[2]-1)|| (a[1]==a[6]+1||a[1]==a[6]-1)|| (a[1]==a[5]+1||a[1]==a[5]-1)|| (a[1]==a[4]+1||a[1]==a[4]-1)) { return false; }else if ((a[2]==a[5]+1||a[2]==a[5]-1)|| (a[2]==a[3]+1||a[2]==a[3]-1)|| (a[2]==a[7]+1||a[2]==a[7]-1)|| (a[2]==a[6]+1||a[2]==a[6]-1)) { return false; }else if ((a[3]==a[6]+1||a[3]==a[6]-1)|| (a[3]==a[7]+1||a[3]==a[7]-1)) { return false; }else if ((a[4]==a[5]+1||a[4]==a[5]-1)|| (a[4]==a[8]+1||a[4]==a[8]-1)|| (a[4]==a[9]+1||a[4]==a[9]-1)) { return false; }else if ((a[6]==a[7]+1||a[6]==a[7]-1)|| (a[6]==a[10]+1||a[6]==a[10]-1)|| (a[6]==a[9]+1||a[6]==a[9]-1)) { return false; }else if (a[7]==a[10]+1||a[7]==a[10]-1) { return false; }else if (a[8]==a[9]+1||a[8]==a[9]-1) { return false; }else if (a[9]==a[10]+1||a[9]==a[10]-1) { return false; }else if ((a[5]==a[6]+1||a[5]==a[6]-1)|| (a[5]==a[10]+1||a[5]==a[10]-1)|| (a[5]==a[9]+1||a[5]==a[9]-1)|| (a[5]==a[8]+1||a[5]==a[8]-1)) { return false; } return true; } }