算法1
时间复杂度 O(2*N) 空间复杂度 O(N)
import java.util.*;
public class Main{
static int N =6;
static int n=-1;
static int [][] arr =new int [NN+1][NN+1];
static int[][] rows = new int [NN+1][NN+1];
static int[][] cols = new int [NN+1][NN+1];
static int[][]recs = new int [NN+1][NN+1];
public static void main(String [] args){
Scanner sc= new Scanner(System.in);
int t= sc.nextInt();
for (int cnt=1;cnt<=t;cnt++){
n = sc.nextInt();
// 矩阵形状 n^2 * n^2
boolean flag = true;
for(int i=1;i<=n*n;i++){
for(int j=1;j<=n*n;j++)
arr[i][j] = sc.nextInt();
}
for(int i=1;i<=n*n;i++){
for(int j=1;j<=n*n;j++){
// 检查 i行 jlie以及 第x哥有无 arr[i][j]了
int x = (i-1)/n*n+ (j-1)/n;
int target =arr[i][j];
if( !check(i,rows,target) || !check(j,cols,target) || !check(x,recs,target) ){
flag = false;
// System.out.println("i:"+i+",j:"+j);
break;
}
}
if(!flag) break;
}
if(flag) System.out.println("Case #"+cnt+": Yes");
else {
System.out.println("Case #"+cnt+": No");
}
rows= new int[N*N+1][N*N+1];
cols = new int[N*N+1][N*N+1];
recs = new int[N*N+1][N*N+1];
}
}
public static boolean check(int row,int[][]arr,int target){
if(target>n*n || arr[row][target]==1){
return false;
}
else{
arr[row][target]=1;
return true;
}
}
}