d*k
发帖数: 207 | 1 请问这正常吗？是不是我的算法还不够好？
我用的方法是dfs，逐行枚举能够放下皇后的位置，对于每个位置，需要O(1)的时间判
断是否能够放下皇后。没有其他剪枝。更新buffer是把当前解存下来，是为了做N-
Queens时候用的。代码如下。
class Solution {
public:
void search(int row, int pos, int* buffer, bool* taken, bool* diag_left_
taken, bool* diag_right_taken, int* count, int row_num) {
if (row == row_num) {
*count += 1;
return;
}
if (pos == row_num) {
return;
}
int diag_left = pos - row + row_num;
int diag_right = pos + row;
if ((!taken[pos]) && (!diag_left_taken[diag_left]) && (!diag_right_
taken[diag_right])) {
taken[pos] = true;
diag_left_taken[diag_left] = true;
diag_right_taken[diag_right] = true;
buffer[row] = pos;
search(row + 1, 0, buffer, taken, diag_left_taken, diag_
right_taken, count, row_num);
taken[pos] = false;
diag_left_taken[diag_left] = false;
diag_right_taken[diag_right] = false;
}
search(row, pos + 1, buffer, taken, diag_left_taken, diag_right_
taken, count, row_num);
}
int totalNQueens(int n) {
int* buffer = new int[n];
bool* taken = new bool[n];
bool* diag_left_taken = new bool[2 * n];
bool* diag_right_taken = new bool[2 * n];
memset(taken, 0, sizeof(bool) * n);
memset(diag_left_taken, 0, sizeof(bool) * 2 * n);
memset(diag_right_taken, 0, sizeof(bool) * 2 * n);
int count = 0;
search(0, 0, buffer, taken, diag_left_taken, diag_right_taken, &
count, n);
return count;
}
}; | d**********x
发帖数: 4083 | 2 大概就是这个数。。。
left_
【在 d*k 的大作中提到】
: 请问这正常吗？是不是我的算法还不够好？
: 我用的方法是dfs，逐行枚举能够放下皇后的位置，对于每个位置，需要O(1)的时间判
: 断是否能够放下皇后。没有其他剪枝。更新buffer是把当前解存下来，是为了做N-
: Queens时候用的。代码如下。
: class Solution {
: public:
: void search(int row, int pos, int* buffer, bool* taken, bool* diag_left_
: taken, bool* diag_right_taken, int* count, int row_num) {
: if (row == row_num) {
: *count += 1;
| d**********x
发帖数: 4083 | 3 另外，N-Queens有O(n)算法
我的世界观已经被颠覆了
left_
【在 d*k 的大作中提到】
: 请问这正常吗？是不是我的算法还不够好？
: 我用的方法是dfs，逐行枚举能够放下皇后的位置，对于每个位置，需要O(1)的时间判
: 断是否能够放下皇后。没有其他剪枝。更新buffer是把当前解存下来，是为了做N-
: Queens时候用的。代码如下。
: class Solution {
: public:
: void search(int row, int pos, int* buffer, bool* taken, bool* diag_left_
: taken, bool* diag_right_taken, int* count, int row_num) {
: if (row == row_num) {
: *count += 1;
| z***2
发帖数: 66 | | d**********x
发帖数: 4083 | 5 http://poj.org/showmessage?message_id=73325
忽略掉初始化矩阵，找一个解的实际cost是O(n)
【在 z***2 的大作中提到】
: O(n) 能解釋一下嗎？
| p*****2
发帖数: 21240 | |
|
