題目描述
方格填數
如下的10個格子
填入0~9的數字，要求：連續的兩個數字不能相鄰，
（左右、上下、對角都算相鄰）
一共有多少種可能的填數方案？
請填寫表示方案數目的整數，
注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字，
解題思路
這也是一題全排列題，這題我是用二維陣列與遞回思想做的
同樣也能用暴力列舉做，但是不提倡，容易出錯，這邊就不展示了
最近連著做了幾題都是差不多型別的題，有興趣的同學可以看看，突破一下這類題型
點擊跳轉【藍橋杯省賽JavaB組真題詳解】湊算式（2016）
點擊跳轉【藍橋杯省賽JavaB組真題詳解】抽簽（2016）
點擊跳轉【藍橋杯省賽JavaB組真題詳解】牌型種數（2015）
參考代碼
public class Main {
static int count = 0;
static int[][] m=new int[3][4];
static boolean[] v=new boolean[10];
public static void main(String[] args) {
m[0][0] = m[2][3] = -2;
dfs(0,1);
System.out.println(count);
}
private static void dfs(int x,int y) {
//這里判斷條件其實也可以在增加個形參計數，但這題條件特殊可以代替
if(m[x][y] == -2) {
count++;
}else {
for (int i = 0; i <= 9; i++) {
if(!v[i] && check(i,x,y)) {
v[i]=true;
m[x][y]=i;
if(y + 1 == 4) {
dfs(x+1, 0);
}else {
dfs(x, y+1);
}
v[i]=false;//回溯
}
}
}
}
//因為是按順序比較，所以只要比較左，上，左上，右上
private static boolean check(int i,int x,int y) {
if (y - 1 >= 0 && Math.abs(m[x][y - 1] - i) == 1) {
return false;
}
if (x - 1 >= 0 && Math.abs(m[x - 1][y] - i) == 1) {
return false;
}
if (x - 1 >= 0 && y - 1 >= 0 && Math.abs(m[x - 1][y - 1] - i) == 1) {
return false;
}
if (x - 1 >= 0 && y + 1 < 4 && Math.abs(m[x - 1][y + 1] - i) == 1) {
return false;
}
return true;
}
}
答案：1580
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261809.html
標籤：其他