使用跳舞链接的精确封面

Question

在经历了这个问题之后，我试图实现Dancing Links来解决确切的覆盖问题，以下是从这里获取并修改的代码(它是列-行结构，我需要行-列结构)。它工作得很好，除了它从未到达Search函数中的成功终止块，我试图跟踪并发现这个

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

是

引起的。示例:对于下面的矩阵

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

我的代码失败cover与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<<"foundn";
        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("%dn",maxResult+1);
    return 0;
}

Answer 1

好的，我再次浏览了源代码并发现了错误，忘记在GetData(void)中增加nRow。这些小虫子令人毛骨悚然!这里是修改后的代码部分，现在它可以完美地工作了。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比应该的值少1，因此用于获取相邻值的内联函数，特别是dataUp()和dataDown()返回了意外值。