方格填数
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。---------结果 1580
图1.jpg
深搜模板：回溯-剪枝
从第一个格子开始，选择0-9数填入并且向右依次填入，每次填完最后一列另起一行。
值得一提的题目中没有明确说明数字不可重复使用，但结果是数字不可重复使用计算的结果1580，一个小技巧灵活用整数除法和取余的特性进行深搜
public class 方格填数 {
static int res = 0;
public static void main(String[] args) {
int [][] arr = new int[3][4];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 4; j++) {//初始化一个较小的数，不产生影响
arr[i][j] = -20;
}
}
dfs(arr, 0, 1);//从第二个方格开始填数
System.out.println(res);
}
private static void dfs(int[][] arr, int x, int y) {
if(x == 2&&y == 3) {//方格填完
res++;
return;//统计下一个情况
}
if(arr[x][y] == -20) {
for(int i = 0 ;i <= 9; i++) {
if(check(i, arr, x, y)&&check2(i, arr, x, y)) {//剪枝
arr[x][y] = i;
dfs(arr, x + (y + 1)/4, (y + 1)%4);
arr[x][y] = -20;//回溯
}
}
}else {
dfs(arr, x + (y + 1)/4, (y + 1)%4);
}
}
//0~9不重复
private static boolean check2(int v, int[][] arr, int x, int y) {
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 4; j++) {
if(v == arr[i][j])
return false;
}
}
return true;
}
//检查左,上,左上,右上不相邻
private static boolean check(int v, int[][] arr, int x, int y) {
int[][] dir = {//这里写全方便理解，真正代码可以按上边注释来写结果相同
{-1, -1},{-1, 0},{-1, 1},
{0, -1}, {0, 1},
{1, -1},{1, 0}, {1, 1}
};
for(int i = 0; i < 8; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 0&&xx < 3&&yy >= 0&&yy < 4) {
if(Math.abs(arr[xx][yy] - v) <= 1)
return false;
}
}
return true;
}
}
网友评论