當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

zcmu-1644 多连块拼图

發(fā)布時(shí)間：2025/3/15 编程问答 13 豆豆

生活随笔收集整理的這篇文章主要介紹了 zcmu-1644 多连块拼图小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

C - 多連塊拼圖

多連塊是指由多個(gè)等大正方形邊與邊連接而成的平面連通圖形。
—— 維基百科

給一個(gè)大多連塊和小多連塊，你的任務(wù)是判斷大多連塊是否可以由兩個(gè)這樣的小多連塊拼成。小多連塊只能平移，不能旋轉(zhuǎn)或者翻轉(zhuǎn)。兩個(gè)小多連塊不得重疊。左下圖是一個(gè)合法的拼法，但右邊兩幅圖都非法。中間那幅圖的問(wèn)題在于其中一個(gè)小多連塊旋轉(zhuǎn)了，而右圖更離譜：拼在一起的那兩個(gè)多連塊根本就不是那個(gè)給定的小多連塊（給定的小多連塊畫(huà)在右下方）。

Input

輸入最多包含20組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)第一行為兩個(gè)整數(shù)n和m(1<=m<=n<=10)。以下n行描述大多連塊，其中每行恰好包含n個(gè)字符或者.，其中表示屬于多連塊，.表示不屬于。以下m行為小多連塊，格式同大多連塊。輸入保證是合法的多連塊（注意，多連塊至少包含一個(gè)正方形）。輸入結(jié)束標(biāo)志為n=m=0。

Output

對(duì)于每組測(cè)試數(shù)據(jù)，如果可以拼成，輸出1，否則輸出0。

Sample Input

4 3 .**. **** .**. .... **. .** ... 3 3 *** *.* *** *.. *.. **. 4 2 **** .... .... .... *. *. 0 0

Sample Output

1 0 0 思路：模擬,記錄小矩形中*號(hào)第一次出現(xiàn)的位置a,b，大矩形中*號(hào)第一次出現(xiàn)的位置 c,d.小矩形與大矩形的映射關(guān)系是 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

總結(jié)

以上是生活随笔為你收集整理的zcmu-1644 多连块拼图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。