ACM模版

描述


题解

之前做的覆盖问题，好像总是 dp ，这次没想到竟然是二分图完美匹配是否唯一。

我学姐的博客对这个题的解释很详细，我感觉凡是我学姐写过的题解，我就没有必要写了，因为我写的题解，任何人都能写出来，可是我学姐写的题解，那可真是精品，详细的令人发指，她不写，应该没有几个人愿意花那么多时间去写吧……

>>>佐理慧的 blog<<<

其实，简单的说，就是我们可以将国际象棋盘看做两个点集，分别是白色格子点集和黑色格子点集，相邻的格子之间连边即可。然后判断是否存在完美的二分图匹配，且唯一。因为很重要的一点我们知道，骨牌覆盖时，总是覆盖住相邻的两个格子，也就是说一个白格子一个黑格子。

具体还是看我学姐的吧！！！

代码

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

using namespace std;

const int MAXN = 2005;
const int d[4][2] = {
  {
  0, 1}, {
  0, -1}, {
  1, 0}, {-1, 0}};
const char S1[6] = "<>^v";
const char S2[6] = "><v^";

int n, m;
char s[MAXN][MAXN];
char ans[MAXN][MAXN];
int deg[MAXN][MAXN];
int Q[MAXN * MAXN][2];

void BFS(int x, int y)
{
    Q[0][0] = x;
    Q[0][1] = y;

    int head = 0, tail = 1;
    while (head < tail)
    {
        x = Q[head][0];
        y = Q[head++][1];
        deg[x][y] = 0;

        for (int i = 0; i < 4; i++)
        {
            int x_ = x + d[i][0];
            int y_ = y + d[i][1];
            if (deg[x_][y_] == 0)
            {
                continue;
            }

            deg[x_][y_] = 0;
            ans[x][y] = S1[i];
            ans[x_][y_] = S2[i];
            for (int t = 0; t < 4; t++)
            {
                int a = x_ + d[t][0];
                int b = y_ + d[t][1];
                if (deg[a][b] == 0)
                {
                    continue;
                }

                deg[a][b]--;
                if (deg[a][b] == 1)
                {
                    Q[tail][0] = a;
                    Q[tail++][1] = b;
                }
            }
        }
    }
}

int main ()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
    }

    int tmp = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '.')
            {
                for (int t = 0; t < 4; t++)
                {
                    tmp++;
                    int x = i + d[t][0];
                    int y = j + d[t][1];
                    if (s[x][y] == '.')
                    {
                        deg[i][j]++;
                    }
                }
            }
        }
    }

    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (deg[i][j] == 1)
            {
                BFS(i, j);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '.' && ans[i][j] == 0)
            {
                flag = false;
                break;
            }
        }
    }

    if (flag)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (!ans[i][j])
                {
                    ans[i][j] = '*';
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            printf("%s\n", ans[i] + 1);
        }
    }
    else
    {
        printf("Not unique\n");
    }

    return 0;
}

参考

《二分图匹配相关》