拆点+最小覆盖数——zoj 1002

主要难点在与拆点

举个例子：

3
. . .
X . X
. X .

在行上拆成

1 1 1

0 2 0

3 0 4

列上拆成

1 3 4

0 3 0

2 0 5

就行了。。。后面一样

#include<stdio.h>
#include<string.h>
bool map[20][20];
int hash[5][5];
int row[5][5];
int lie[5][5];
int mark[20];
bool flag[20];
int m;
bool dfs(int x)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(map[x][i]==0||flag[i]) continue;

        flag[i]=1;
        if(mark[i]==0||dfs(mark[i]))
        {
            mark[i]=x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int i,g,k,j;
    int count;
    while(scanf("%d",&k),k)
    {
        getchar();
        m=g;
        memset(map,0,sizeof(map)); 
        memset(row,0,sizeof(row));
        memset(lie,0,sizeof(lie));

        for(i=1;i<=k;i++)
        {
            for(j=1;j<=k;j++)
            {
                char temp;
                scanf("%c",&temp);
                if(temp=='X')hash[i][j]=1;
                else hash[i][j]=0;
            }
            getchar();
        }

        int add=0;
        for(i=1;i<=k;i++)//行上的点拆分
        {
            for(j=1;j<=k;j++)
            {
                if(hash[i][j]==0)
                {
                    add++;
                    while(hash[i][j]==0&&j<=k)
                    {
                        row[i][j]=add;
                        j++;
                    }
                    j--;
                }
                else
                {    
                    while(hash[i][j]==1&&j<=k)j++;
                    j--;
                }
            }
        }g=add;

        add=0;
        for(j=1;j<=k;j++)//列上的点拆分
        {
            for(i=1;i<=k;i++)
            {
                if(hash[i][j]==0)
                {
                    add++;
                    while(hash[i][j]==0&&i<=k)
                    {
                        lie[i][j]=add;
                        i++;
                    }
                    i--;
                }
                else
                {    
                    while(hash[i][j]==1&&i<=k)i++;
                    i--;
                }
            }
        }m=add;

        int x,y;
        for(i=1;i<=k;i++)//点标记到二分图
        {
            for(j=1;j<=k;j++)
            {
                map[row[i][j]][lie[i][j]]=1;
            }
        }


        memset(mark,0,sizeof(mark));
        count=0;

        for(i=1;i<=g;i++)
        {
            memset(flag,0,sizeof(flag));
            
            if(dfs(i)==1) count++;
        }

        printf("%d\n",count);
    }
}