Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

三剪齐下

Posted by uuuouou at 2015-01-11 22:42:16 on Problem 3435
#include <cstdio>
#include <cstring>

int N, M, cell[101][101];
bool row[101][101];
bool col[101][101];
bool box[101][101];

inline int BoxID(int r, int c){
	return (r - 1) / N * N + (c - 1) / N + 1;
}
bool dfs(int i, int j)
{
	if(i > M) return true;
	if(j > M || cell[i][j]) return dfs(i + 1, 1);

	int b = BoxID(i, j);
	for(int x = 1; x <= M; ++x){
		if(row[i][x] || col[j][x] || box[b][x]) continue;
		
		cell[i][j] = x;
		row[i][x] = col[j][x] = box[b][x] = true;
		if(dfs(i, j + 1)) return true;
		row[i][x] = col[j][x] = box[b][x] = false;
	}
	return false;
}

int main()
{
	int i, j, k, b;
	bool valid;
	while(~scanf("%d", &N)){
		//initialize
		M = N * N;
		for(i = 1; i <= M; ++i){
			memset(row[i]+1, false, M);
			memset(col[i]+1, false, M);
			memset(box[i]+1, false, M);
		}
		//input
		valid = true;
		for(i = 1; i <= M; ++i){
			for(j = 1; j <= M; ++j){
				scanf("%d", &k);
				cell[i][j] = k;
				if(k == 0) continue;
				if(row[i][k]) valid = false;
				else row[i][k] = true;
				if(col[j][k]) valid = false;
				else col[j][k] = true;
				b = BoxID(i, j);
				if(box[b][k]) valid = false;
				else box[b][k] = true;
			}
		}
		//check
		if(valid && dfs(1, 1)) puts("CORRECT");
		else puts("INCORRECT");
	}
	return 0;	
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator