经过this question之后我尝试实现 Dancing Links 以仅解决确切的封面问题，以下是取自 here 的代码并修改(它是Column-Row结构，我需要Row-Column结构)。它工作正常，只是它永远不会到达 Search 函数中的成功终止 block ，我试图追踪并发现这个

RowNode = Column->Down ; RowNode!=Column ; RowNode = RowNode->Down

是造成它的原因。示例:对于以下矩阵

1 2 3 4
1 1 x x
x 1 1 x
x x 1 1

我的代码无法用Header=4覆盖最后一列

我该如何克服这个问题？这是完整的代码

#include <iostream>
#include <vector>
#include <cstdio>
#include <stdbool.h>

#define MAX_ROW 50L
#define MAX_COL 100L

using namespace std;

struct str_node {
    struct str_node * Header;
    struct str_node * Left;
    struct str_node * Right;
    struct str_node * Up;
    struct str_node * Down;
    int HeaderID,RowIndex,ColIndex;
};


int nCol;
int nRow;
struct str_node Matrix[MAX_ROW][MAX_COL];
vector<struct str_node*>ResultRow;
struct str_node Root;
struct str_node *RootNode = &Root;
bool Data[MAX_ROW][MAX_COL];
int maxResult;

//functions to get the neighbours (are circular)
inline int dataLeft(int i) { return (i-1 < 0) ? nCol-1 : i-1 ; }
inline int dataRight(int i) { return (i+1) % nCol ; }
inline int dataUp(int i) { return (i-1 < 0) ? nRow-1 : i-1 ; }
inline int dataDown(int i) { return (i+1) % nRow ; }

void CreateToroidalMatrix(void) {

    int a,b, i, j;

    for(a = 0 ; a <= nRow ; a++) {

        for(b=0 ; b < nCol ; b++) {

            if(Data[a][b]) {

                Matrix[a][b].RowIndex = a;
                Matrix[a][b].ColIndex = b;

                // Left pointer
                i = a; j = b; do {j = dataLeft(j); } while (!Data[i][j]);
                Matrix[a][b].Left = &Matrix[i][j];

                // Right pointer
                i = a; j = b; do {j = dataRight(j); } while (!Data[i][j]);
                Matrix[a][b].Right = &Matrix[i][j];

                // Up pointer
                i = a; j = b; do {i = dataUp(i); } while (!Data[i][j]);
                Matrix[a][b].Up = &Matrix[i][j];

                // Down pointer
                i = a; j = b; do {i = dataDown(i); } while (!Data[i][j]);
                Matrix[a][b].Down = &Matrix[i][j];

                //Head pointer
                Matrix[a][b].Header = &Matrix[0][b];
                Matrix[a][b].HeaderID = b+1;

            }
        }
    }

    //Initialize root
    RootNode->Right = &Matrix[0][0];
    RootNode->Left = &Matrix[0][nCol-1];
    Matrix[0][0].Left = RootNode;
    Matrix[0][nCol-1].Right = RootNode;
}

void Cover(struct str_node *ColNode){

    cout<<"Covering header node "<<ColNode->HeaderID<<'\n';

    struct str_node *RowNode, *RightNode;

    ColNode->Right->Left = ColNode->Left;
    ColNode->Left->Right = ColNode->Right;

    for(RowNode = ColNode->Down ; RowNode!=ColNode ; RowNode = RowNode->Down) {
        for(RightNode = RowNode->Right ; RightNode!=RowNode ; RightNode = RightNode->Right) {
            RightNode->Up->Down = RightNode->Down;
            RightNode->Down->Up = RightNode->Up;
        }
    }
}

void UnCover(struct str_node *ColNode) {
    //uncover the covered nodes to find a different solution
    struct str_node *RowNode, *LeftNode;

    for(RowNode = ColNode->Up; RowNode!=ColNode; RowNode = RowNode->Up) {
        for(LeftNode = RowNode->Left; LeftNode!=RowNode; LeftNode = LeftNode->Left) {
            LeftNode->Up->Down = LeftNode;
            LeftNode->Down->Up = LeftNode;
        }
    }
    ColNode->Right->Left = ColNode;
    ColNode->Left->Right = ColNode;
}

void Search(int k){

    //all columns covered

    if( RootNode->Right == RootNode){
        cout<<"found\n";
        if(maxResult < k)
            maxResult = k;
        return;
    }

    //if not covered
    else{

        struct str_node *Column = RootNode->Right;
        struct str_node *RowNode;
        struct str_node *RightNode;
        struct str_node *LeftNode;

        Cover(Column);

        for( RowNode = Column->Down ; RowNode!=Column ; RowNode = RowNode->Down){

            ResultRow.push_back(RowNode);

            for(RightNode = RowNode->Right; RightNode!=RowNode; RightNode = RightNode->Right)
                Cover(RightNode->Header);

            Search(k+1);
            RowNode = ResultRow.back();
            ResultRow.pop_back();
            Column = RowNode->Header;

            for(LeftNode = RowNode->Left; LeftNode!=RowNode; LeftNode = LeftNode->Left)
                UnCover(LeftNode->Header);
        }
        UnCover(Column);
    }
}

void GetData(void){
    int pos,k;
    scanf("%d%d",&nCol, &nRow);

    for(int i=0 ; i<nCol ; i++)
        Data[0][i] = true;

    for(int i=1 ; i<=nRow ; i++){
        scanf("%d",&k);
        for(int j=0 ; j<k ; j++){
            scanf("%d",&pos);
            Data[i][pos-1] = true;
        }
    }
    CreateToroidalMatrix();
}

int main(void){
    GetData();
    Search(0); // from level 0
    printf("%d\n",maxResult+1);
    return 0;
}

最佳答案

好吧，我再次查看源代码并发现了错误，忘记在 GetData(void) 中增加 nRow。这些小 bug 令人毛骨悚然!所以这里是代码的修改部分，现在它可以完美运行。 nRow 必须增加一次，因为我为每一列的 Header 使用了额外的一行。

void GetData(void){
    int pos,k;
    scanf("%d%d",&nCol, &nRow);

    nRow++;//this is the change

    for(int i=0 ; i<nCol ; i++)
        Data[0][i] = true;

    for(int i=1 ; i<nRow ; i++){
        scanf("%d",&k);
        for(int j=0 ; j<k ; j++){
            scanf("%d",&pos);
            Data[i][pos-1] = true;
        }
    }
    CreateToroidalMatrix();
}

这个循环在 CreateToroidalMatrix()

for(a=0 ; a<nRow ; a++) // removed equal sign

由于 nRow 比应有的少了一个，用于获取邻居的内联函数，特别是 dataUp() 和 dataDown() 返回了意外的值。

关于c++ - 使用 Dancing Links 精确覆盖，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22418934/