学步园

【转载请注明出处: http://blog.csdn.net/lzl124631x】

OJ: https://code.google.com/codejam/contest/2929486/dashboard#s=p0

非数独矩阵的判定条件:

1. 矩阵内存在[1, N]范围外的数字;
2. 每一个检测单元(行, 列, N*N的正方形)内不恰好是[1, N]的N个数字. 在1成立的条件下说明该检测单元内有重复的数据.

思路:

• 对每个检测单元进行验证, 一旦满足上述判定条件立即返回false
• 设置一个长度为N的tag数组, 元素初始全为0. 每读入一个数据(若该数据不在[1, N]的范围内则返回false)将其对应的tag置1, 如果在设置之前该tag就已经为1说明有重复数据, 返回false.

关键点:

• 对N*N正方形内元素的索引

代码:

#include <stdio.h>
#include <string.h>
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define PRINTCASE printf("Case #%d: ",case_n++)
#define PRINTCASE_ printf("Case #%d:\n",case_n++)
#define MAX_N 6

int mtx[MAX_N * MAX_N][MAX_N * MAX_N] = {0};

int test_valid(int N){
	int tag[MAX_N * MAX_N] = {0};
	int i, j;
	// test each row
	for(i = 0; i < N * N; i++){
		memset(tag, 0, sizeof(tag));
		for(j = 0; j < N * N; j++){
			if(mtx[i][j] < 1 || mtx[i][j] > N * N || tag[mtx[i][j] - 1] == 1) 
				return 0;
			tag[mtx[i][j] - 1] = 1;
		}
	}
	// test each column
	for(i = 0; i < N * N; i++){
		memset(tag, 0, sizeof(tag));
		for(j = 0; j < N * N; j++){
			if(tag[mtx[j][i] - 1] == 1) 
				return 0;
			tag[mtx[j][i] - 1] = 1;
		}
	}
	// test each N * N square
	for(i = 0; i < N * N; i++){
		memset(tag, 0, sizeof(tag));
		for(j = 0; j < N * N; j++){
			if(tag[mtx[i / N * N + j / N][i % N * N + j % N] - 1] == 1) 
				return 0;
			tag[mtx[i / N * N + j / N][i % N * N + j % N] - 1] = 1;
		}
	}
	return 1;
}

int main(){
	int N, i, j;
	freopen("A-large-practice.in","r",stdin);
	freopen("out.txt","w",stdout);
	CASET{
		scanf("%d", &N);
		for(i = 0; i < N * N; i++){
			for(j = 0; j < N * N; j++){
				scanf("%d", &mtx[i][j]);
			}
		}
		PRINTCASE;
		printf("%s\n", test_valid(N)? "Yes" : "No");
	}
	return 0;
}