Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474258
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类: C/C++

2010-04-04 13:23:35



给一个01矩阵, 求哪些行能使每一列正好有一个1.

这是Donald E.Knuth介绍dancing link时用的一个例子。
 论文中文翻译在
 原文PDF下载在
我中英文对照着看的,翻译的跟原文意思差不多, 算是很好了。
多看几遍理解了舞蹈步骤基本上就能做了,  就是搞十字链表很麻烦,还要构造比较好的数据结构,一开始我搞复杂化了,  要么超空间,要么指针指错误,  调试了n遍,重写了一遍终于一个个问题都解决了。

虽然Accept了,可是花了5s+, 汗。。。。  优化空间还很大,只是不知道怎么搞了。

#include <stdio.h>
#include <string.h>
#define N 1000 //最多N行N列

#define inf 10000000
int posx[N][N], posy[N][N];

typedef struct Node
{
  int key;
  int cnt; //此列有几个1

  struct Node *root; //指向列头

  struct Node *up;
  struct Node *down;
  struct Node *left;
  struct Node *right;
}Node;

Node link[N*N]; //十字链表

int column, raw; //列数,行数

int flag, top, stack[N];

int build()
{
    int i, j;
    int cur, pre, first;

    //构造列头, link[0]是head,link[1]---link[column]是列头, link[column]之后的是有1的节点
    for(i=1; i<=column; i++)
    {
        link[i-1].right = &link[i];
        link[i].left = &link[i-1];
        link[i].cnt = 0;
        link[i].key = i;
    }
    link[0].left = &link[column];
    link[0].key = 0;
    link[column].right = &link[0];
    
    /*deal with column*/
    for(i=1; i<=column; i++)
    {
        cur = posy[i][1] * N + i;
        pre = cur;
        link[cur].up = &link[i];
        link[i].down = &link[cur];
        link[cur].root = &link[i];
        link[cur].key = cur;
        link[i].cnt++;
        for(j=2; j<=posy[i][0]; j++)
        {
            cur = posy[i][j] * N + i;
            link[pre].down = &link[cur];
            link[cur].key = cur;
            link[cur].up = &link[pre];
            link[cur].root = &link[i];
            link[i].cnt++;
            pre = cur;
        }
        link[pre].down = &link[i];
        link[i].up = &link[pre];
        
        if(link[i].cnt == 0)
            return 0;
    
    }

    /*deal with rows*/
    for(i=1; i<=raw; i++)
    {
        first = i*N+posx[i][1];
        pre = first;
        for(j=2; j<=posx[i][0]; j++)
        {
            cur = i*N+posx[i][j];
            link[pre].right = &link[cur];
            link[cur].left = &link[pre];
            pre = cur;
        }
        link[pre].right = &link[first];
        link[first].left = &link[pre];
    }
//    print();
    return 1;
}

//移除列,同时把一行上的1都移除
void remove1(Node *c)
{
    Node *p, *q;
    c->left->right = c->right;
    c->right->left = c->left;

    for(p=c->down; p->key!=c->key; p=p->down)
    {
            p->root->cnt--;
        for(q=p->right; q->key!=p->key;q=q->right)
        {
        
            q->down->up = q->up;
            q->up->down = q->down;
        }
    }
}

//把移除的恢复
void resume(Node *c)
{
    Node *p, *q;
    c->right->left = c;
    c->left->right = c;
    for(p=c->up; p->key!=c->key; p=p->up)
    {
        p->root->cnt++;
        for(q=p->left; q->key!=p->key; q=q->left)
        {
        
            q->up->down = q;
            q->down->up=q;
        }
    }
}

int dfs(int k)
{
    int i;
    int s;
    Node *c, *p, *q;

    if(flag)
        return 1;
    if(link[0].right == &link[0])
    {
        printf("%d", top);
        for(i=0; i<top; i++)
            printf(" %d", stack[i]);
        printf("\n");
        flag = 1;
        return 1;
    }

    //找到1最少的列, 这个不搞也行,只是为了优化
    s = inf;
    for(p=link[0].right; p->key != link[0].key; p=p->right)
    {
        if(p->cnt < s)
        {
            s = p->cnt;
            c = p;
        }
    }
    remove1(c);
    /*    printf("after remove %d: \n",c->key);//////////////////
        print();/////////////////////////////////////////
*/

    for(p=c->down; p->key!=c->key; p=p->down)
    {
        stack[top++] = p->key/N;
        for(q=p->right; q->key!=p->key; q=q->right)
        {
            remove1(q->root);
        }
        if(dfs(k+1))
            return 1;
        for(q=p->left; q->key!=p->key; q=q->left)
        {
            resume(q->root);
        }
        top--;
    }
    resume(c);
    return 0;
}

int main()
{
  int i, j, tmp;
 
  freopen("1017.in", "r", stdin);
  while(scanf("%d %d", &raw, &column) != EOF)
  {
     memset(posx, 0, sizeof(posx));
     memset(posy, 0, sizeof(posy));
     memset(stack, 0, sizeof(stack));
     memset(link, 0, sizeof(link));
    for(i=1; i<=raw; i++)
    {
      scanf("%d", &posx[i][0]);
      for(j=1; j<=posx[i][0]; j++)
      {
        scanf("%d", &tmp);
        posx[i][j] = tmp;
        posy[tmp][++posy[tmp][0]] = i;
      }
    }

    if(build() == 0)
    {
        printf("NO\n");
        continue;
    }
    
    flag = 0;
    top = 0;
    dfs(0);

    if(!flag)
        printf("NO\n");
  }
  return 0;
  
}


阅读(1560) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~