题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
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[] rows = new int[9], cols = new int[9], grids = new int[9]; // 这里写错了写成了boolean[] 数组
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;
}
}
find(0, 0, matrix, rows, cols, grids);
for (int i = 0; i < 9; i++) {
System.out.println(String.valueOf(matrix[i]));
}
}
public static boolean find(int row, int col, char[][] matrix, int[] rows, int[] cols, int[] grids) {
if (col == 9) {
col = 0;
row++;
if (row == 9) return true;
}
if (matrix[row][col] != '.') {
return find(row, col + 1, matrix, rows, cols, grids);
} else {
for (int num = 1; num <= 9; num++) {
int pos = row / 3 * 3 + col / 3;
if ((1 << num & rows[row]) != 0 || (1 << num & cols[col]) != 0 || (1 << num & grids[pos]) != 0) continue;
rows[row] ^= 1 << num;
cols[col] ^= 1 << num;
grids[pos] ^= 1 << num;
matrix[row][col] = (char) ('0' + num);
if (find(row, col + 1, matrix, rows, cols, grids)) return true;
rows[row] ^= 1 << num;
cols[col] ^= 1 << num;
grids[pos] ^= 1 << num;
matrix[row][col] = '.';
}
}
return false;
}
}