0 0 投票数

#include <stdio.h>
#include <iostream>

#define WIDTH 3
#define BOARD_SIZE 9
#define CANDIDATES_RANGE 9

const int SCORE_WEIGHT[BOARD_SIZE][BOARD_SIZE] = {
{6, 6, 6, 6, 6,  6, 6, 6, 6},
{6, 7, 7, 7, 7,  7, 7, 7, 6},
{6, 7, 8, 8, 8,  8, 8, 7, 6},
{6, 7, 8, 9, 9,  9, 8, 7, 6},
{6, 7, 8, 9, 10, 9, 8, 7, 6},
{6, 7, 8, 9, 9,  9, 8, 7, 6},
{6, 7, 8, 8, 8,  8, 8, 7, 6},
{6, 7, 7, 7, 7,  7, 7, 7, 6},
{6, 6, 6, 6, 6,  6, 6, 6, 6}
};

int board[BOARD_SIZE][BOARD_SIZE] = {{0}};

int ans = -1;

// 暴力搜索会超时 case 5，改成标记
//int isValid(int row, int col, int val) {
//    for (int i = 0; i < BOARD_SIZE; i++)
//        if (i != row && board[i][col] == val)
//            return false;
//    for (int j = 0; j < BOARD_SIZE; j++)
//        if (j != col && board[row][j] == val)
//            return false;
//    int majorRow = row / WIDTH;
//    int majorCol = col / WIDTH;
//    for (int i = majorRow * WIDTH; i < majorRow * WIDTH + WIDTH; i++)
//        for (int j = majorCol * WIDTH; j < majorCol * WIDTH + WIDTH; j++)
//            if (i != row && j != col && board[i][j] == val)
//                return false;
//    return true;
//}

// 以 rowUsed 为例，rowUsed[i][j] == true 表示第 i 行的数字 j 已经出现过
bool rowUsed[BOARD_SIZE][CANDIDATES_RANGE + 1] = {{0}};
bool colUsed[BOARD_SIZE][CANDIDATES_RANGE + 1] = {{0}};
bool gridUsed[BOARD_SIZE][CANDIDATES_RANGE + 1] = {{0}};

bool isValid(int row, int col, int val) {
return (!rowUsed[row][val] && !colUsed[col][val] && !gridUsed[row / WIDTH * WIDTH + col / WIDTH][val]);
}

void setNumber(int row, int col, int val, bool status) {
board[row][col] = status ? val : 0;
colUsed[col][val] = status;
rowUsed[row][val] = status;
gridUsed[row / WIDTH * WIDTH + col / WIDTH][val] = status;
}

int calculateScore() {
int score = 0;
for (int i = 0; i < BOARD_SIZE; i++)
for (int j = 0; j < BOARD_SIZE; j++)
score += board[i][j] * SCORE_WEIGHT[i][j];
return score;
}

void dfs(int depth, int candidatesNumber) {
if (depth == candidatesNumber) {
ans = std::max(calculateScore(), ans);
return;
}

/*
* 这里有个 trick，可能要看了题解（数据）才知道了
* i 从 0 到 9，j 从 0 到 9，case 3 和 case 4 会超时，从 9 反过来回到 0 就不会
* 本质上没有区别，只是数据恶心了些
*/
for (int i = BOARD_SIZE - 1; i >= 0; i--)
for (int j = BOARD_SIZE - 1; j >= 0; j--) {
if (board[i][j] != 0)
continue;
for (int candidate = 1; candidate <= CANDIDATES_RANGE; candidate++) {
if (isValid(i, j, candidate)) {
setNumber(i, j, candidate, true);
dfs(depth + 1, candidatesNumber);
setNumber(i, j, candidate, false);
}
}
return; // 这个 return 必须要剪枝，9个数都放完了就 return，否则会很慢很慢很慢，样例都过不了
}

}

int main() {
int candidatesNumber = 0;
for (int i = 0; i < BOARD_SIZE; i++)
for (int j = 0; j < BOARD_SIZE; j++) {
int x;
scanf("%d", &x);
setNumber(i, j, x, true);
if (x == 0)
candidatesNumber++;
}
dfs(0, candidatesNumber);
printf("%d", ans);
return 0;
}
0 0 投票数

（可选）如果您也有个人网站，不妨分享一下

0 评论