| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
三剪齐下#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator