HDU OJ 4185 Oil Skimming [이분 도의 흑백 염색]

원제 연결:http://acm.hdu.edu.cn/showproblem.php?pid=4185
제목: 제목 이 쓰레기 처럼 묘사 되 어 있다.간단하게 문제 중의 그림 을 보고 최대 몇 쌍 의 \ # 을 구하 세 요. (인접 한 두 개 는 한 쌍 입 니 다)
코드:

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max = 19000;
vector<int>V[Max];
int link[Max],use[Max];
char Map[700][700];
int  Dye_loop[700][700];
struct hh
{
    int x,y;
    bool operator <(const hh &t1)const
    {
        return x<t1.x||x==t1.x&&y<t1.y;
    }
};
void init(int n)
{
    int i;
    for(i=0;i<=n;i++)
      V[i].clear();
}
bool Dfs(int v)
{
    int i,j,k;
    for(i=0;i<V[v].size();i++)
    {
        k=V[v][i];
        if(!use[k])
        {
            use[k]=1;
            if(!link[k]||Dfs(link[k]))
            {
                link[k]=v;
                return true;
            }
        }
    }
    return false;
}
int MaxMatch(int n)
{
    int i,j,ans=0;
    memset(link,0,sizeof(link));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(Dfs(i))
            ans++;
    }
    return ans;

}
void Dye_Dfs(int x,int y,int z,int n)
{
    //printf("x: %d  y: %d   z: %d
",x,y,z);
    Dye_loop[x][y] = z;
    if(x-1>=1&&Dye_loop[x-1][y]==0&&Map[x-1][y]=='#')
    {
        if(z == 1)
            Dye_Dfs(x-1,y,2,n);
        if(z == 2)
            Dye_Dfs(x-1,y,1,n);
    }
    if(y-1>=1&&Dye_loop[x][y-1]==0&&Map[x][y-1]=='#')
    {
        if(z == 1)
            Dye_Dfs(x,y-1,2,n);
        if(z == 2)
            Dye_Dfs(x,y-1,1,n);
    }
    if(x+1<=n&&Dye_loop[x+1][y]==0&&Map[x+1][y]=='#')
    {
        if(z == 1)
            Dye_Dfs(x+1,y,2,n);
        if(z == 2)
            Dye_Dfs(x+1,y,1,n);
    }
    if(y+1<=n&&Dye_loop[x][y+1]==0&&Map[x][y+1]=='#')
    {
        if(z == 1)
            Dye_Dfs(x,y+1,2,n);
        if(z == 2)
            Dye_Dfs(x,y+1,1,n);
    }
}
//void display_dye(int n)
//{
//    int i,j;
//    for(i=1;i<=n;i++)
//    {
//        for(j=1;j<=n;j++)
//            cout<<Dye_loop[i][j]<<" ";
//        cout<<endl;
//    }
//}
void Dye(int n)
{
    int i,j;
    memset(Dye_loop,0,sizeof(Dye_loop));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(Dye_loop[i][j]==0&&Map[i][j] == '#')
                Dye_Dfs(i,j,1,n);
        }
    }
}
int Build(int n)
{
    int i,j,k;
    int mn=0,sum=0;
    map<hh,int>M;
    map<hh,int>::iterator it;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(Dye_loop[i][j] == 1)
            {
                sum++;
                int x , y;
                x = i-1 , y = j;
                if(x>=1&&Dye_loop[x][y]==2)
                {
                   struct hh t1={x,y};
                   it = M.find(t1);
                   if(it!=M.end())//ok
                   {
                       V[sum].push_back((*it).second);
                   }
                   else
                   {
                       M[t1] = ++mn;
                       V[sum].push_back(mn);
                   }
                }
                x = i ,y = j-1;
                if(y>=1&&Dye_loop[x][y]==2)
                {
                   struct hh t1={x,y};
                   it = M.find(t1);
                   if(it!=M.end())//ok
                   {
                       V[sum].push_back((*it).second);
                   }
                   else
                   {
                       M[t1] = ++mn;
                       V[sum].push_back(mn);
                   }
                }
                x = i+1 , y = j;
                if(x<=n&&Dye_loop[x][y]==2)
                {
                   struct hh t1={x,y};
                   it = M.find(t1);
                   if(it!=M.end())//ok
                   {
                       V[sum].push_back((*it).second);
                   }
                   else
                   {
                       M[t1] = ++mn;
                       V[sum].push_back(mn);
                   }
                }
                x = i , y = j+1;
                if(y<=n&&Dye_loop[x][y]==2)
                {
                   struct hh t1={x,y};
                   it = M.find(t1);
                   if(it!=M.end())//ok
                   {
                       V[sum].push_back((*it).second);
                   }
                   else
                   {
                       M[t1] = ++mn;
                       V[sum].push_back(mn);
                   }
                }
            }
        }
    }
    return sum;
}
int main()
{
    int i,j,n,m,k,ncase;
    scanf("%d",&ncase);
    for(k=1;k<=ncase;k++)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%s",Map[i]+1);
        Dye(n);
        //display_dye(n);
        m =Build(n);

        printf("Case %d: ",k);

        printf("%d
",MaxMatch(m));

        init(m);
    }
}

쓰레기 로 썼어 요. xiaod 가 time 0 코드 를 달라 고 해서 경 배 를 붙 였 어 요!!

#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 36005;
const int M = 100005;

struct Vertex
{
    int head;
}V[N];

struct Edge
{
    int v,next;
}E[M];

int n,m,top,match[N];

bool used[N];

char str[N][N];

const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};

void Init()
{
    top = 0;
    memset(V,-1,sizeof(V));
}

void Add_Edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
}

bool dfs(int u)
{
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(!used[v])
        {
            used[v] = true;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxMatch(int n)
{
    int ans = 0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if(dfs(i))
            ++ans;
    }
    return ans;
}

int main()
{
    int z,__n,ncase=0;
    scanf("%d",&z);
    map< pair<int,int>,int > M[2];
    while(z--)
    {
        Init();
        M[0].clear();
        M[1].clear();
        scanf("%d",&__n);
        n = 0 , m = 0;
        for(int i=1;i<=__n;i++)
            scanf("%s",str[i]+1);
        for(int i=1;i<=__n;i++)
        {
            for(int j=1;str[i][j];j++)
            {

                if(str[i][j] != '#')
                    continue;
                int k = (i+j)&1;
                if(!k)
                {
                    M[0][make_pair(i,j)] = ++n;
                    int u = n;
                    for(int ii=0;ii<4;ii++)
                    {
                        int x = i + dx[ii] , y = j + dy[ii];
                        if(!(x>=1 && x<=__n && y>=1 && y<=__n && str[x][y]=='#'))
                            continue;
                        int v;
                        if(M[1].count(make_pair(x,y)))
                            v = M[1][make_pair(x,y)];
                        else
                            v = M[1][make_pair(x,y)] = 18000 + (++m);
                        Add_Edge(u,v);
                    }
                }
                else
                {
                    if(!M[1].count(make_pair(i,j)))
                        M[1][make_pair(i,j)] = 18000 + (++m);
                }
            }
        }
//        for(map< pair<int,int>,int >::iterator it=M[0].begin();it!=M[0].end();++it)
//            printf("(%d,%d)
",it->first.first,it->first.second);
        printf("Case %d: %d
",++ncase,maxMatch(n));
    }
    return 0;
}