（匹配）Fire Net --hdu --1045

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1045

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82834#problem/A

一看原题，先用搜索写一下，还是要学学匹配吧！

以前的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10
#define INF 0x3f3f3f3f

int n, ans;
char G[N][N];

bool judge(int x, int y)
{
    int i;

    if(G[x][y]=='X')
        return false;

    for(i=x; i>=0; i--)
    {
        if(G[i][y]=='X')
            break;
        if(G[i][y]=='D')
            return false;
    }

    for(i=y; i>=0; i--)
    {
        if(G[x][i]=='X')
            break;
        if(G[x][i]=='D')
            return false;
    }
    return true;
}

void DFS(int z, int k)
{
    int x, y;

    x = z/n;
    y = z%n;

    if(z==n*n)
    {
        ans = max(ans, k);
        return ;
    }

    if(judge(x, y))
    {
        G[x][y] = 'D';
        DFS(z, k+1);
        G[x][y] = '.';
    }

    DFS(z+1, k);
}

int main()
{
    while(scanf("%d", &n),n)
    {
        int i;

        memset(G, 0, sizeof(G));
        for(i=0; i<n; i++)
            scanf("%s", G[i]);

        ans = 0;
        DFS(0, 0);

        printf("%d
", ans);
    }
    return 0;
}

不懂什么意思，先贴上

匹配的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f

struct node{int x, y;}a[N][N];

int n, p[N], used[N], x, y, G[N][N];
char s[N][N];

int Find(int u)
{
    for(int i=1; i<=y; i++)
    {
        if(!used[i] && G[u][i])
        {
            used[i]=1;
            if(!p[i] || Find(p[i]))
            {
                p[i] = u;
                return true;
            }
        }
    }
    return false;
}


int main()
{
    while(scanf("%d", &n),n)
    {
        int i, j;

        memset(s, 0, sizeof(s));
        for(i=0; i<n; i++)
            scanf("%s", s[i]);

        x = y = 0;
        for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(s[i][j]=='.')
            {
                if(j==0 || s[i][j-1]=='X')
                    x++;
                a[i][j].x = x;
            }
            if(s[j][i]=='.')
            {
                if(j==0 || s[j-1][i]=='X')
                    y++;
                a[j][i].y = y;
            }
        }

        memset(G, 0, sizeof(G));
        for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(s[i][j]=='.')
            {
                int u = a[i][j].x;
                int v = a[i][j].y;
                G[u][v] = 1;
            }
        }

        int ans= 0;
        memset(p, 0, sizeof(p));
        for(i=1; i<=x; i++)
        {
            memset(used, 0, sizeof(used));
            if(Find(i)==true)
                ans++;
        }

        printf("%d
", ans);
    }
    return 0;
}