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

## Re:实测剪枝dfs可过

Posted by chliul at 2014-01-01 21:23:41 on Problem 3074
In Reply To:附上强剪条件 Posted by:damacheng009 at 2010-10-26 15:49:26
```就是楼上说的两种。。。正推和反算即可。。。帖份代码给不想dance的同学们研究下吧。。。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

struct node{
int x;
int y;
int option;
bool optionList[9];
};

int table[9][9];
bool row[9][9];
bool col[9][9];
bool block[9][9];
node order[81];

int cmp(const node& a, const node& b) {
return a.option < b.option;
}

void init() {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(block, 0, sizeof(block));
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(table[i][j] != 0) {
row[i][table[i][j]-1] = true;
col[j][table[i][j]-1] = true;
block[i/3*3 + j/3][table[i][j]-1] = true;
}
}
}
}

void updateOption(int l) {
int rowOption[9][9] = {};
int colOption[9][9] = {};
int blockOption[9][9] = {};
for(int index = 0; index < l; index++) {
int i = order[index].x;
int j = order[index].y;
if(table[i][j] == 0) {
order[index].option = 0;
memset(order[index].optionList, 0, sizeof(order[index].optionList));
for(int k = 0; k < 9; k++) {
if(!row[i][k] && !col[j][k] && !block[i/3*3 + j/3][k]) {
order[index].option++;
order[index].optionList[k] = true;
rowOption[i][k]++;
colOption[j][k]++;
blockOption[i/3*3 + j/3][k]++;
}
}
}
}
for(int n = 0; n < 9; n++) {
for(int k = 0; k < 9; k++) {
if(rowOption[n][k] == 1) {
for(int index = 0; index < l; index++) {
if(table[order[index].x][order[index].y] == 0) {
if(order[index].x == n && order[index].optionList[k]) {
order[index].option = 1;
memset(order[index].optionList, 0, sizeof(order[index].optionList));
order[index].optionList[k] = true;
}
}
}
}
if(colOption[n][k] == 1) {
for(int index = 0; index < l; index++) {
if(table[order[index].x][order[index].y] == 0) {
if(order[index].y == n && order[index].optionList[k]) {
order[index].option = 1;
memset(order[index].optionList, 0, sizeof(order[index].optionList));
order[index].optionList[k] = true;
}
}
}
}
if(blockOption[n][k] == 1) {
for(int index = 0; index < l; index++) {
if(table[order[index].x][order[index].y] == 0) {
if(order[index].x/3*3 + order[index].y/3 == n && order[index].optionList[k]) {
order[index].option = 1;
memset(order[index].optionList, 0, sizeof(order[index].optionList));
order[index].optionList[k] = true;
}
}
}
}
}
}
}

int getOrder() {
memset(order, 0, sizeof(order));
int index = 0;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(table[i][j] == 0) {
order[index].x = i;
order[index].y = j;
index++;
}
}
}
updateOption(index);
return index;
}

void inputOne(int i, int j, int k) {
row[i][k] = true;
col[j][k] = true;
block[i/3*3+j/3][k] = true;
table[i][j] = k+1;
}

void outputOne(int i, int j, int k) {
row[i][k] = false;
col[j][k] = false;
block[i/3*3+j/3][k] = false;
table[i][j] = 0;
}

int getIndex(int l) {
int option = 10;
int res = -1;
for(int index = 0; index < l; index++) {
int i = order[index].x;
int j = order[index].y;
if(table[i][j] == 0) {
if(order[index].option < option) {
option = order[index].option;
res = index;
}
}
}
if(option == 0) {
return -1;
}
else {
return res;
}
}

bool dfs(int cnt, int l) {
if(cnt == l)
return true;
int index = getIndex(l);
if(index == -1)
return false;
int i = order[index].x;
int j = order[index].y;
for(int k = 0; k < 9; k++) {
if(order[index].optionList[k]) {
inputOne(i, j, k);
updateOption(l);
if(dfs(cnt + 1, l)) {
return true;
}
outputOne(i, j, k);
updateOption(l);
}
}
return false;
}

int main() {
char tmp[82] = {};
while(scanf("%s", tmp) && strcmp(tmp, "end") != 0) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(tmp[i*9 + j] == '.') {
table[i][j] = 0;
}
else {
table[i][j] = tmp[i*9 + j] - '0';
}
}
}
init();
int l = getOrder();

dfs(0, l);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
printf("%d", table[i][j]);
}
}
printf("\n");
}
}
```

Followed by: