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