HDU 1045 Fire Net(DFS or bipartite graph match)

Description

给出一个地图，有空地，有墙，在空地上安排炮台，炮台会向四方攻击，但不会穿透墙壁，要避免炮台彼此攻击到，求最多能安排多少炮台？

Analyze

可以简单のDFS

另外的二分图匹配：

假设没有墙壁，为每行、每列标号，针对每个点进行建边，求最大匹配

1	1	1	1
2	2	2	2
3	3	3	3
4	4	4	4

1	2	3	4
1	2	3	4
1	2	3	4
1	2	3	4

建边add(1, 1)add(1, 2)add(1, 3)add(1,4)add(2,1)……

在求最大匹配时，假设第一个表中的2匹配了第二个表中的3，那么相当于在第二行第三列建一座炮台，由于本行都是2，且2已经被分配，所以本行不会再被分配炮台；同理，本列都是3，且3已经被分配，所以本列不会再被分配炮台。如此限制了同行或同列不会出现两座炮台。

现在有墙，标号便可增加了，比如样例

4
.X..
....
XX..
....

1	X	2	2
3	3	3	3
X	X	4	4
5	5	5	5

1	X	5	6
1	3	5	6
X	X	5	6
2	4	5	6

Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 205;
char s[N][N];
int n, mat[N], idr, idc, gr[N][N], gc[N][N];
bool vis[N], g[N][N];

bool dfs(int u)
{
    for (int v = 1; v <= idc; v++)
    {
        if (vis[v] || !g[u][v])
            continue;
        vis[v] = 1;
        if (!mat[v] || dfs(mat[v]))
        {
            mat[v] = u;
            return 1;
        }
    }
    return 0;
}

int main()
{
    while (scanf("%d", &n), n)
    {
        memset(g, false, sizeof(g));
        memset(gr, 0, sizeof(gr));
        memset(gc, 0, sizeof(gc));
        memset(mat, 0, sizeof(g));
        for (int i = 0; i < n; i++)
            scanf("%s", s[i]);

        idr = 0;
        for (int i = 0; i < n; i++)
        {
            idr++;
            for (int j = 0; j < n; j++)
            {
                if (s[i][j] == 'X')
                {
                    if (j != 0 && j != n - 1)
                        idr++;
                    continue;
                }
                gr[i][j] = idr;
            }
        }
        idc = 0;
        for (int j = 0; j < n; j++)
        {
            idc++;
            for (int i = 0; i < n; i++)
            {
                if (s[i][j] == 'X')
                {
                    if (i != 0 && i != n - 1)
                        idc++;
                    continue;
                }
                gc[i][j] = idc;
            }
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (s[i][j] == 'X')
                    continue;
                int u = gr[i][j], v = gc[i][j];
                g[u][v] = true;
            }
        }

        int ans = 0;
        for (int i = 1; i <= idr; i++)
        {
            memset(vis, false, sizeof(vis));
            if (dfs(i))
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Code of DFS

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, ans;
char mp[10][10];

bool check(int x, int y)
{
    if(mp[x][y] != '.')
        return 0;
    for(int i = y - 1; i >= 0; --i)
        if(mp[x][i] == 'B')
            return 0;
        else if(mp[x][i] == 'X')
            break;
    for(int i = x - 1; i >= 0; --i)
        if(mp[i][y] == 'B')
            return 0;
        else if(mp[i][y] == 'X')
            break;
    return 1;
}

void DFS(int pos, int num)
{
    if(pos == n * n)
    {
        ans = max(ans, num);
        return ;
    }
    int x = pos / n, y = pos % n;
    if(check(x, y))
    {
        mp[x][y] = 'B';
        DFS(pos + 1, num + 1);
        mp[x][y] = '.';
    }
    DFS(pos + 1, num);
    return ;
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%s", mp[i]);
        ans = 0;
        DFS(0, 0);
        cout << ans << '\n';
    }
    return 0;
}