卧薪尝胆,厚积薄发。
Drazil and Tiles
Date: Thu Oct 18 20:13:07 CST 2018 In Category: NoCategory

Description:

给一个 $n\times m$ 的棋盘,可以摆放 $1\times2$ 或 $2\times1$ 的骨牌,构造一个方案或判断无解。
$1\leqslant n,m\leqslant 2000$

Solution:

首先如果有一个点他周围只有一个空位,那他的摆放方式是确定的,可以直接确定,摆放后又有一些周围只有一个空位的,可以用一个类似拓扑排序的方法用一个队列依次进行这些操作。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cctype>
#include<cstring>
using namespace std;
inline char getc()
{
register char c = getchar();
while(c != '.' && c != '*')c = getchar();
return c;
}
int n,m;
#define MAXN 2010
char c[MAXN][MAXN];
int deg[MAXN][MAXN];
int mx[4] = {0,0,1,-1};
int my[4] = {1,-1,0,0};
char cx[4] = {'<','>','^','v'};
char cy[4] = {'>','<','v','^'};
#define fi first
#define se second
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
c[i][j] = getc();
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
for(int k = 0;k < 4;++k)
if(c[i + mx[k]][j + my[k]] != 0 && c[i + mx[k]][j + my[k]] != '*')
++deg[i][j];
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
if(deg[i][j] == 0 && c[i][j] == '.')
{
puts("Not unique");
return 0;
}
}
}
queue< pair<int,int> > q;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
if(c[i][j] == '.' && deg[i][j] == 1)
q.push(make_pair(i,j));
while(!q.empty())
{
pair<int,int> k = q.front();q.pop();
for(int i = 0;i < 4;++i)
{
if(c[k.fi + mx[i]][k.se + my[i]] == '.')
{
c[k.fi][k.se] = cx[i];
c[k.fi + mx[i]][k.se + my[i]] = cy[i];
int xx = k.fi + mx[i],yy = k.se + my[i];
for(int j = 0;j < 4;++j)
{
if(c[xx + mx[j]][yy + my[j]] == '.')
{
--deg[xx + mx[j]][yy + my[j]];
if(deg[xx + mx[j]][yy + my[j]] == 1)
{
q.push(make_pair(xx + mx[j],yy + my[j]));
}
}
}
}
}
}
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
if(c[i][j] == '.')
{
puts("Not unique");
return 0;
}
}
}
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
putchar(c[i][j]);
}
puts("");
}
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡