题目描述
blablabla
样例
blablabla
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[][] matrix = new char[9][];
for(int i = 0; i < 9; i) {
matrix[i] = sc.nextLine().toCharArray();
}
int[] grids = new int[9];
int[] rows = new int[9];
int[] cols = new int[9];
check(matrix, grids, rows, cols);
find(0, 0, matrix, grids, rows, cols);
for (int i = 0; i < 9; i) {
System.out.println(String.valueOf(matrix[i]));
}
}
public static void check(char[][] matrix, int[] grids, int[] rows, int[] cols) {
for (int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if (matrix[i][j] == '.') continue;
int num = matrix[i][j] - '0';
rows[i] ^= 1 << num;
cols[j] ^= 1 << num;
grids[i / 3 * 3 + j / 3] ^= 1 << num; // 这里是 j / 3我写成了j % 3 比如第二个grid id = 1 row = 0 col = 5
// 0 / 3 * 3 + 5 / 3 = 1 换成 5 % 3 = 2 就错了
}
}
}
public static boolean find(int row, int col, char[][] matrix, int[] grids, int[] rows, int[] cols) {
if (col == 9) {
col = 0;
row++;
if (row == 9) return true;
}
if (matrix[row][col] != '.') {
return find(row, col + 1, matrix, grids, rows, cols);
} else {
for (int num = 1; num <= 9; num++) {
int place = row / 3 * 3 + col / 3;
if ((1 << num & rows[row]) != 0 || (1 << num & cols[col]) != 0 || (1 << num & grids[place]) != 0) continue;
rows[row] ^= 1 << num;
cols[col] ^= 1 << num;
grids[place] ^= 1 << num;
matrix[row][col] = (char) (num + '0');
if (find(row, col + 1, matrix, grids, rows, cols)) return true;
rows[row] ^= 1 << num;
cols[col] ^= 1 << num;
grids[place] ^= 1 << num;
matrix[row][col] = '.';
}
}
return false;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla