Appoint description:
System Crawler (Aug 12, 2016 9:32:14 AM)
System Crawler (Aug 12, 2016 9:32:14 AM)
Description
多连块是指由多个等大正方形边与边连接而成的平面连通图形。![ACM: NBUT 1105 多连块拼图 - 水题 - 模拟-LMLPHP]( "ACM: NBUT 1105 多连块拼图 - 水题 - 模拟-LMLPHP")
-- 维基百科
给一个大多连块和小多连块，你的任务是判断大多连块是否可以由两个这样的小多连块拼成。小多连块只能平移，不能旋转或者翻转。两个小多连块不得重叠。左下图是一个合法的拼法，但右边两幅图都非法。中间那幅图的问题在于其中一个小多连块旋转了，而右图更离谱：拼在一起的那两个多连块根本就不是那个给定的小多连块（给定的小多连块画在右下方）。
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
1
0
0
/*/
中文题： 模拟题，模拟去用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;
}