AcWing 703. 数独检查-java
原题链接
简单
作者:
上杉
,
2021-02-01 23:31:11
,
所有人可见
,
阅读 326
空间换时间,建立数组标记对应行、列、方格是否已经出现
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
for (int m = 1; m <= T ; m++) {
int n = input.nextInt();
//一行有 n个块,每块有n列
int[][] grid = new int[n*n][n*n];
int[][] row = new int[n * n][(n+1) * (n+1)];
int[][] col = new int[n * n][(n+1) * (n+1)];
int[][] div = new int[n * n][(n+1) * (n+1)];
for (int i = 0; i < n * n; i++) {
for (int j = 0; j < n * n; j++) {
grid[i][j] = input.nextInt();
}
}
boolean flag = true;
for (int i = 0; i < n * n; i++) {
if (flag){
for (int j = 0; j < n * n; j++) {
// 第 i 行出现了 grid[i][j]
// 第 j 列出现了 grid[i][j]
// 第 i / n j / n 个格子出现了
int num = grid[i][j];
if (num > n * n || num <= 0){
flag = false;
break;
}
if(row[i][num] == 1){
//System.out.println("行重复了:"+i+": "+num);
flag = false;
break;
}else {
row[i][num] = 1;
}
if(col[j][num] == 1){
//System.out.println("列重复了:"+j+": "+num);
flag = false;
break;
}else {
col[j][num] = 1;
}
int r = i / n;//第 r 行,从0开始
int c = j / n;//第 c 列,从0开始
int divNum = r * n + c;
if (div[divNum][num] == 1){
//System.out.println("块重复了:"+divNum+": "+num);
flag = false;
break;
}else {
div[divNum][num] = 1;
}
}
}
}
String res = flag?"Yes":"No";
//Case #1: Yes
System.out.println("Case #"+m+":"+res);
}
}
}