2016年第七届蓝桥杯java B组省赛试题方格填数

深藏阁楼爱情的钟 2022-05-28 00:30 147阅读 0赞

如下的10个格子

\+--+--+--+  
| | | |  
\+--+--+--+--+  
| | | | |  
\+--+--+--+--+  
| | | |  
\+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。  
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

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

思路：

因为是个填空题，所以直接采取暴力方法枚举10个数的全排列判断是否满足条件即可

对格子是否满足条件的判断只需要判断一个格子的下，左，右，左下，右下，即可，并且注意边界条件的判定防止数组的越界

public class Main {
    	static int ANS = 0;
    	static int[][] map = new int[3][4];
    	static int[] num = new int[10];
    	static int[] visit = new int[10];
    
    	static boolean check() {
    		for (int i = 0; i < 3; i++) {
    			for (int j = 0; j < 4; j++) {
    				if (i + 1 < 3) {
    					if (Math.abs(map[i + 1][j] - map[i][j]) == 1) {
    						return false;
    					}
    					if (j + 1 < 4) {
    						if (Math.abs(map[i + 1][j + 1] - map[i][j]) == 1) {
    							return false;
    						}
    					}
    					if (j - 1 >= 0) {
    						if (Math.abs(map[i][j] - map[i + 1][j - 1]) == 1) {
    							return false;
    						}
    					}
    				}
    				if (j + 1 < 4) {
    					if (Math.abs(map[i][j + 1] - map[i][j]) == 1) {
    						return false;
    					}
    				}
    				if (j - 1 >= 0) {
    					if (Math.abs(map[i][j] - map[i][j - 1]) == 1) {
    						return false;
    					}
    				}
    
    			}
    		}
    		return true;
    	}
    
    	static void qpl(int n) {
    		if (n == 10) {
    			int ans = 0;
    			for (int i = 0; i < 3; i++) {
    				for (int j = 0; j < 4; j++) {
    					if (i == 0 && j == 0) {
    						continue;
    					}
    					if (ans == 10) {
    						break;
    					}
    					map[i][j] = num[ans++];
    				}
    			}
    			if (check()) {
    				ANS++;
    			}
    			return;
    		}
    		for (int i = 0; i < 10; i++) {
    			if (visit[i] == 0) {
    				num[n] = i;
    				visit[i] = 1;
    				qpl(n + 1);
    				visit[i] = 0;
    			}
    		}
    
    	}
    
    	public static void main(String[] args) {
    		map[0][0] = -10;
    		map[2][3] = -10;
    		qpl(0);
    		System.out.println(ANS);
    	}
    }