描述
题解
之前做的覆盖问题,好像总是 dp ,这次没想到竟然是二分图完美匹配是否唯一。
我学姐的博客对这个题的解释很详细,我感觉凡是我学姐写过的题解,我就没有必要写了,因为我写的题解,任何人都能写出来,可是我学姐写的题解,那可真是精品,详细的令人发指,她不写,应该没有几个人愿意花那么多时间去写吧……
其实,简单的说,就是我们可以将国际象棋盘看做两个点集,分别是白色格子点集和黑色格子点集,相邻的格子之间连边即可。然后判断是否存在完美的二分图匹配,且唯一。因为很重要的一点我们知道,骨牌覆盖时,总是覆盖住相邻的两个格子,也就是说一个白格子一个黑格子。
具体还是看我学姐的吧!!!
代码
#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;
}