ACM: NBUT 1105 多连块拼图 - 水题

NBUT 1105 多连块拼图

Time Limit:1000MS Memory Limit:65535KB 64bit IO Format:

Appoint description:
System Crawler (Aug 12, 2016 9:32:14 AM)

Description

多连块是指由多个等大正方形边与边连接而成的平面连通图形。

-- 维基百科

给一个大多连块和小多连块，你的任务是判断大多连块是否可以由两个这样的小多连块拼成。小多连块只能平移，不能旋转或者翻转。两个小多连块不得重叠。左下图是一个合法的拼法，但右边两幅图都非法。中间那幅图的问题在于其中一个小多连块旋转了，而右图更离谱：拼在一起的那两个多连块根本就不是那个给定的小多连块（给定的小多连块画在右下方）。

Input

输入最多包含20组测试数据。每组数据第一行为两个整数n和m(1<=m<=n<=10)。以下n行描述大多连块，其中每行恰好包含n个字符*或者.，其中*表示属于多连块，.表示不属于。以下m行为小多连块，格式同大多连块。输入保证是合法的多连块（注意，多连块至少包含一个正方形）。输入结束标志为n=m=0。

Output

对于每组测试数据，如果可以拼成，输出1，否则输出0。

Sample Input

4 3

.**.

****

.**.

....

**.

.**

...

3 3

***

*.*

***

*..

*..

**.

4 2

****

....

....

....

*.

*.

0 0

Sample Output

/*/

中文题：

模拟题，模拟去用n个完全相同小块覆盖大块。

仔细想一下啊，用小块能够覆盖掉大块的话有且只有一种覆盖方式，而且大块某个点只能由小块的某点覆盖。

这样就简单了，我的做法用，先找从速往下到小块的第一个*号，然后DFS搜一下整个小块的以第一个*为【0，0】的所有坐标。

然后到大块里面去找，从上往下找到第一个*，把小块的每一个坐标覆盖过的位 置全部该成 ‘.’ 记录下一共改了多少个点【前面记录大块一共有多少个点】。

如果相同就说明成功覆盖，否则不能。

AC代码

/*/

#include"algorithm"

#include"iostream"

#include"cstring"

#include"cstdlib"

#include"cstdio"

#include"string"

#include"vector"

#include"queue"

#include"cmath"

#include"map"

using namespace std;

typedef long long LL ;

#define memset(x,y) memset(x,y,sizeof(x))

#define memcpy(x,y) memcpy(x,y,sizeof(x))

#define FK(x) cout<<"["<<x<<"]\n"

#define bigfor(T)  for(int qq=1;qq<= T ;qq++)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct Box {

	int x,y;

	Box(int xx,int yy):x(xx),y(yy) {};

	Box() {};

} into[123];

int n,m;

int num2,num;

int erear;

char maps[20][20],box[20][20],sox[20][20],vis[20][20];

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

void init() {

	erear=0;

	memset(vis,0);

}

void DFS(int x,int y,int tox,int toy) {

	if(!vis[x][y]) {

		vis[x][y]=1;

		into[erear++]=Box(tox,toy);//记录box的覆盖坐标

		for(int i=0; i<4; i++) {

			int xx=x+dir[i][0];

			int yy=y+dir[i][1];

			if(xx<0||yy<0||xx>=m||yy>=m)continue;

			if(box[xx][yy]!='*')continue;

			if(vis[xx][yy])continue;

			DFS(xx,yy,tox+dir[i][0],toy+dir[i][1]);

		}

	}

}

int main() {

	while(~scanf("%d%d",&n,&m)) {

		if(!n&&!m)break;

		num=0;

		num2=0;

		for(int i=0; i<n; i++) {

			scanf("%s",maps[i]);

			for(int j=0; j<n; j++) {

				if(maps[i][j]=='*')num++;

			}

		}

		for(int i=0; i<m; i++) {

			scanf("%s",box[i]);

			for(int j=0; j<m; j++) {

				if(box[i][j]=='*')num2++;

			}

		}

		if(num%num2) {

			puts("0");

			continue;

		}

		int stx,sty;

		int flag=1;

		init();

		for(int i=0; i<m; i++) {

			for(int j=0; j<m; j++) {

				if(box[i][j]=='*') {

					DFS(i,j,0,0);

					flag=0;

				}

				if(!flag)break;

			}

			if(!flag)break;

		}

//		for(int i=0;i<erear;i++){

//			cout<<"x "<<into[i].x<<" y "<<into[i].y<<endl;

//		}

		int tot=0;

		flag=0;

		for(int i=0; i<n; i++) {

			for(int j=0; j<n; j++) {

				if(maps[i][j]=='*') {

					for(int k=0; k<erear; k++) {

						if(maps[i+into[k].x][j+into[k].y]!='*') {//模拟覆盖。

							flag=1;

							break;

						}

						maps[i+into[k].x][j+into[k].y]='.';

						tot++;

					}

					if(flag)break;

				}

				if(flag)break;

			}

		}

//		puts("");

//		for(int i=0;i<n;i++){

//			puts(maps[i]);

//		}

//		puts("");

		if(tot==num)puts("1");

		else puts("0");

	}

	return 0;

}

巴特西

ACM: NBUT 1105 多连块拼图 - 水题 - 模拟

最新文章

热门文章