原文链接http://www.cnblogs.com/zhouzhendong/p/8990658.html

题目传送门 - CodeForces 516B

题意

　　给出一个$n\times m$的矩形。其中有些位置已经被覆盖。

　　现在让你用$1\times 2$的小矩形来覆盖其他地方，小矩形不能重叠。

　　如果有多种覆盖方案，或者无法把没被覆盖的地方全部覆盖，那么输出特殊信息。否则输出唯一的方案。

　　$n,m\leq 2000$

题解

　　乍一看，我还以为是经典的二分图匹配题目。但是由于$n,m$都很大，所以不行。

　　注意到题意概括中第$3$行的特殊性。

　　我们考虑这样一个算法：

　　首先，如果原矩阵中有被四面包围的空地，那么显然无解。

　　对于原矩阵中被三面包围的空地，显然只有一种方法可以填充这个空地。

　　我们考虑使用一个队列，一开始加入被三面包围的空地，然后在填充的过程中，影响到了其他的空地，并加入新的待填充空地。

　　在填充的过程中可以顺便判掉某些无解的情况。

　　如果按照上述操作，无法把矩阵填充满，那么就是无解或者多解了。

　　至于多解的情况，很显然，任何一块连通空地如果不能找到被三面包围的空地，那么显然有多种方案来填充。

　　至于为什么，自己yy。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2005;

int dx[4]={ 0, 0, 1,-1};

int dy[4]={-1, 1, 0, 0};

int n,m;

char g[N][N];

int head=0,tail=0,x[N*N],y[N*N];

bool flag=1;

void ckadd(int i,int j){

	if (g[i][j]!='.')

		return;

	int cnt=0;

	for (int k=0;k<4;k++)

		if (g[i+dx[k]][j+dy[k]]=='.')

			cnt++;

	if (cnt==1)

		tail++,x[tail]=i,y[tail]=j;

	if (cnt==0)

		flag=0;

}

int main(){

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++)

		scanf("%s",g[i]+1);

	for (int i=1;i<=n;i++)

		g[i][0]=g[i][m+1]='*';

	for (int i=1;i<=m;i++)

		g[0][i]=g[n+1][i]='*';

	for (int i=1;i<=n;i++)

		for (int j=1;j<=m;j++)

			ckadd(i,j);

	while (head<tail&&flag){

		head++;

		int i=x[head],j=y[head];

		if (g[i][j]!='.')

			continue;

		int cnt=0;

		for (int k=0;k<4;k++)

			if (g[i+dx[k]][j+dy[k]]=='.'){

				cnt++;

				if (k==0)

					g[i][j]='>',g[i+dx[k]][j+dy[k]]='<';

				if (k==1)

					g[i][j]='<',g[i+dx[k]][j+dy[k]]='>';

				if (k==2)

					g[i][j]='^',g[i+dx[k]][j+dy[k]]='v';

				if (k==3)

					g[i][j]='v',g[i+dx[k]][j+dy[k]]='^';

				for (int t=0;t<4;t++)

					ckadd(i+dx[k]+dx[t],j+dy[k]+dy[t]);

			}

		if (cnt==0)

			flag=0;

	}

	for (int i=1;i<=n;i++)

		for (int j=1;j<=m;j++)

			if (g[i][j]=='.')

				flag=0;

	if (!flag)

		puts("Not unique");

	else {

		for (int i=1;i<=n;i++,puts(""))

			for (int j=1;j<=m;j++)

				putchar(g[i][j]);

	}

	return 0;

}

巴特西

CodeForces 516B Drazil and Tiles 其他

题目传送门 - CodeForces 516B

题意

题解

代码

最新文章

热门文章