题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
List<String> res = new ArrayList<>();
for (int k = 1; k <= T; k++) {
int n = sc.nextInt();
int[][] matrix = new int[n * n][n * n];
for (int i = 0; i < n * n; i++) {
for (int j = 0; j < n * n; j++) {
matrix[i][j] = sc.nextInt();
}
}
String s = "Case #" + k + ": " + helper(matrix, n);
res.add(s);
}
for (String s : res) System.out.println(s);
}
public static String helper(int[][] matrix, int n) {
// 之前为什么过不了因为我用的位运算只有32位(这里只用了31位) 导致 N= 6时候 N * N = 36 会越界 所以不能状态压缩只能set判定
Map<Integer, Set<Integer>> rows = new HashMap<>();
Map<Integer, Set<Integer>> cols = new HashMap<>();
Map<Integer, Set<Integer>> blocks = new HashMap<>();
for (int i = 0; i < n * n; i++) {
rows.put(i, new HashSet<>());
cols.put(i, new HashSet<>());
blocks.put(i, new HashSet<>());
}
boolean flag = false;
for (int i = 0; i < n * n; i++) {
for (int j = 0; j < n * n; j++) {
int num = matrix[i][j];
Set<Integer> curRow = rows.get(i);
Set<Integer> curCol = cols.get(j);
Set<Integer> curBlock = blocks.get(i / n * n + j / n); // 原本是 i / 3 * 3 + j / 3 变成
// i / n * n + j / n
if (num > n * n || curRow.contains(num) || curCol.contains(num) || curBlock.contains(num)) {
flag = true;
break;
}
curRow.add(num);
curCol.add(num);
curBlock.add(num);
}
if (flag) break;
}
if (flag) return "No";
return "Yes";
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla