生活随笔
收集整理的這篇文章主要介紹了
zcmu-1644 多连块拼图
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
C - 多連塊拼圖
多連塊是指由多個等大正方形邊與邊連接而成的平面連通圖形。
—— 維基百科
給一個大多連塊和小多連塊，你的任務是判斷大多連塊是否可以由兩個這樣的小多連塊拼成。小多連塊只能平移，不能旋轉或者翻轉。兩個小多連塊不得重疊。左下圖是一個合法的拼法，但右邊兩幅圖都非法。中間那幅圖的問題在于其中一個小多連塊旋轉了，而右圖更離譜：拼在一起的那兩個多連塊根本就不是那個給定的小多連塊（給定的小多連塊畫在右下方）。
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
思路：模擬,記錄小矩形中*號第一次出現的位置a,b，大矩形中*號第一次出現的位置 c,d.小矩形與大矩形的映射關系是 g[i][j] <---> G[c+i-a][d+j-b],匹配兩次即可。代碼：
#include<cstdio>
using namespace std;
int n,m,a,b,c,d,flag;
char s1[15][15],s2[15][15];void preb()
{bool flag=true;for(int i=0; i<m; i++)for(int j=0; j<m; j++){if(s2[i][j]=='*'&&flag){flag=false;a=i;b=j;}}
}void prea()
{bool flag=true;for(int i=0; i<n; i++)for(int j=0; j<n; j++){if(s1[i][j]=='*'&&flag){flag=false;c=i;d=j;}}
}int judge()
{preb();prea();for(int i=0; i<m; i++)for(int j=0; j<m; j++){if(s2[i][j]=='*'){if(s1[i+c-a][j+d-b]=='*')s1[i+c-a][j+d-b]='.';else return 0;}}prea();for(int i=0; i<m; i++)for(int j=0; j<m; j++){if(s2[i][j]=='*'){if(s1[i+c-a][j+d-b]=='*')s1[i+c-a][j+d-b]='.';else return 0;}}return 1;
}
int main()
{while(~scanf("%d%d",&n,&m)){if(n==0&&m==0)break;getchar();for(int i=0; i<n; i++)scanf("%s",s1[i]);for(int i=0; i<m; i++)scanf("%s",s2[i]);if(judge())printf("1\n");else printf("0\n");}return 0;
}
Hint
總結
以上是生活随笔為你收集整理的zcmu-1644 多连块拼图的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
