4

在经历了这个问题之后，我尝试实现 Dancing Links 以仅解决确切的覆盖问题，以下是从这里获取并修改的代码（它是 Column-Row 结构，我需要 Row-Column 结构）。它工作正常，只是它永远不会到达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<<"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;
}
4

1 回答 1

1

好的，我再次浏览了源代码并发现了错误，忘记增加nRowin GetData(void)。这些小虫子令人毛骨悚然！所以这里是代码的修改部分，现在它完美地工作了。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()意外值。

于 2014-03-16T03:37:23.083 回答