Polyomino Composer

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.

- Wikipedia

Given a large polyomino and a small polyomino, your task is to determine whether you can compose the large one with two copies of the small one. The polyominoes can be translated, but not flipped or rotated. The two pieces should not overlap. The leftmost picture below is a correct way of composing the large polyomino, but the right two pictures are not. In the middle picture, one of the pieces was rotated. In the rightmost picture, both pieces are exactly identical, but they're both rotated from the original piece (shown in the lower-right part of the picture).

Input 

There will be at most 20 test cases. Each test case begins with two integers n and m ( 1mn10) in a single line. The next n lines describe the large polyomino. Each of these lines contains exactly n characters in `*',`.'. A `*' indicates an existing square, and a `.' indicates an empty square. The next m lines describe the small polyomino, in the same format. These characters are guaranteed to form valid polyominoes (note that a polyomino contains at least one existing square). The input terminates with n = m = 0, which should not be processed.

Output 

Sample Input 

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

Sample Output 

1
0
0

The Seventh Hunan Collegiate Programming Contest
Problemsetter: Rujia Liu, Special Thanks: Yiming Li & Jane Alam Jan

題目描述：

不經過旋轉及翻轉，問一張圖形有沒有可能被兩個小圖形拼湊出來，而且不會互相重疊。

題目解法：

由於給定的小圖示都是正方形，且是連通圖，但是拼湊的時候可能會有多餘的小圖示會超過邊界。

先抓一點小圖示的非空點，然後去對應大圖示的其中一個點，接著去塗滿它。

接著再抓一點沒被使用過的點，再塗第二次，中間檢查是否有碰撞。

#include <stdio.h>
#include <string.h>
char g1[50][50], g2[50][50];
int used[15][15], used2[15][15], err;
int n, m;
void dfs(int x, int y, int vx, int vy) {
    if(x < 0 || y < 0 || x >= m || y >= m)
        return;
    if(err || g2[x][y] == '.' || used2[x][y])
        return;
    if(vx < 0 || vy < 0 || vx >= n || vy >= n || g1[vx][vy] == '.' || used[vx][vy] == 1)
        err = 1;
    used2[x][y] = 1;
    used[vx][vy] = 1;
    dfs(x+1, y, vx+1, vy);
    dfs(x-1, y, vx-1, vy);
    dfs(x, y+1, vx, vy+1);
    dfs(x, y-1, vx, vy-1);
}
int main() {
    int i, j, k, p, q, r, a, b, c;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        for(i = 0; i < n; i++)
            scanf("%s", &g1[i]);
        for(i = 0; i < m; i++)
            scanf("%s", &g2[i]);
        int px, py;
        for(i = 0; i < m; i++) {
            for(j = 0; j < m; j++) {
                if(g2[i][j] == '*') {
                    px = i, py = j;
                    i = m, j = m;
                }
            }
        }
        int ret = 0;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                if(g1[i][j] == '*') {
                    memset(used, 0, sizeof(used));
                    memset(used2, 0, sizeof(used2));
                    err = 0;
                    dfs(px, py, i, j);
                    if(err) continue;
                    for(p = 0; p < n; p++) {
                        for(q = 0; q < n; q++) {
                            if(g1[p][q] == '.' || used[p][q])
                                continue;
                            memset(used2, 0, sizeof(used2));
                            err = 0;
                            dfs(px, py, p, q);
                            if(err) continue;
                            ret = 1;
                            p = n, q = n, i = n, j = n;
                        }
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}