AcWing 183. 靶形数独(Java 暴搜)
原题链接
中等
作者:
Limited
,
2021-02-09 20:25:37
,
所有人可见
,
阅读 302
要点
- 同AcWing 166. 数独(Java 暴搜)
- 需要修改的位置:本题需要枚举所有可行方案,并求出其分值取最大
- 递归下一层时,不需要判断返回值再
return
,直接还原现场即可
- 求分值时,某方格权重 = 初始权重6 + 该方格到四个边界的距离最小值
代码
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
// ans 存最终的和 初始值-1 所以若无解直接输出即可
static int N = 9, ans = -1;
// 打表
static int[] ones = new int[1 << N], map = new int[1 << N];
// 记录行、列、九宫格的数字使用状态 其中九宫格索引为 (x/3*3 + y/3)
static int[] row = new int[N], col = new int[N], cell = new int[N];
// 存数独矩阵 注意数值偏移了1位 1~9 ===> 0~8
static int[][] f = new int[N][N];
static int lowbit(int x) {
return x & (-x);
}
static int getCellIndex(int x, int y) {
return x / 3 * 3 + y / 3;
}
static int getStatus(int x, int y) {
return row[x] & col[y] & cell[getCellIndex(x, y)];
}
static boolean dfs(int n) {
if (n == 0) { // n为待填空位总数 n=0时有解 遍历矩阵f统计分数
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// f[i][j] 所存数字偏移了1位 1~9 ===> 0~8
// 每个格子的分值 = (该格数字+偏移量1) * (初始权重6 + 该格到边界的距离)
sum += (f[i][j] + 1) * (6 + Math.min(Math.min(i, j), N - 1 - Math.max(i, j)));
}
}
// 更新ans
ans = Math.max(ans, sum);
return true;
}
// 遍历找到可选方案数最小的格子
int minv = Integer.MAX_VALUE, x = -1, y = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (f[i][j] < 0) {
int temp = ones[getStatus(i, j)];
if (temp == 0) { // 如果可选方案数为0 证明当前方案无解 直接返回
return false;
} else if (temp < minv) { // 若可选方案数较小 更新坐标(x,y)和方案数minv
minv = temp;
x = i;
y = j;
}
}
}
}
// 尝试所有可选方案 注意更新row、col、cell和还原现场
for (int i = getStatus(x, y); i > 0; i -= lowbit(i)) {
int t = map[lowbit(i)];
f[x][y] = t;
row[x] -= 1 << t;
col[y] -= 1 << t;
cell[getCellIndex(x, y)] -= 1 << t;
dfs(n - 1);
f[x][y] = -1;
row[x] += 1 << t;
col[y] += 1 << t;
cell[getCellIndex(x, y)] += 1 << t;
}
return false;
}
public static void main(String[] args) {
// 打表
for (int i = 0; i < N; i++) {
map[1 << i] = i;
}
for (int i = 0; i < (1 << N); i++) {
for (int j = i; j > 0; j -= lowbit(j)) {
ones[i]++;
}
}
// row、col、cell的初始状态为 111111111 表示数字0~8均可用
Arrays.fill(row, (1 << N) - 1);
Arrays.fill(col, (1 << N) - 1);
Arrays.fill(cell, (1 << N) - 1);
int n = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
f[i][j] = scanner.nextInt() - 1; // 所存数字偏移1位
if (f[i][j] >= 0) {
row[i] -= 1 << f[i][j];
col[j] -= 1 << f[i][j];
cell[getCellIndex(i, j)] -= 1 << f[i][j];
} else {
n++;
}
}
}
dfs(n);
System.out.println(ans);
}
}