Ships

Probably everyone who ever attended school knows the game where twoopposing players place a set of ships on a sheet of paper and try toeliminate each other's ships by guessing their location.

In our version of the game, your opponent has distributed the followingseven ship patterns over a rectangular grid of squares:

                      xx   xx     xx   x       x    x                      xx    xx   xx    xxx   xxx   xxx   xxxx

Each ship pattern covers exactly four squares. The patterns may berotated but not mirrored. All patterns are guaranteed to be placedcompletely within the boundaries of the rectangle and not to overlap eachother, whereas touching another pattern or the border is allowed.

We assume that we are in the middle of the game and that severalsquares have already been uncovered. You will be given a rectangular grid ofsquares representing your current knowledge about the positions of yourenemy's ships. Every square is marked by one of the following characters:

• `x' if a ship covers the square
• `o' if no ship covers the square
• `.' if the square has not yet been uncovered

Given that information, you are to decide whether you can determine allremaining `x' squares with at most one miss, i.e. whether youcould uncover the `.' squares withoutgetting more than one `o' square before you had all `x'squares uncovered. This means youare allowed to hit a `o' if then the solution becomes unique.

Input

The input file contains several game situations. Every test case startswith a line containing two integers w and h. These define width andheight of the game rectangle, where .

Each of the next h lines contains a string of w characters. Each ofthese characters is either `x', `o' or `.', dependingon the state of the corresponding square.

A blank line separates each game from the next. The input file endswith a game having w = 0 and h = 0. This game should not be processed.

Output

For each test case you should first output a line containing the numberof the game, followed by a line containing either `yes.'(if you can determine all `x' with at most one miss) or`no.' (if you cannot determine all `x' without at least two misses).

Output a blank line after every game.

Sample Input

10 10.x..x.....oooooxoooooxooxxx...xxoooooo..xoooxooo..ooxxxxoo..oooooxxooxooooooxooxooooooooxxoooooooooo0 0

Sample Output

Game #1yes.

[解題思路]：
由於題目要求猜測船隻所在，想像海上的雷達偵測，只能知道形狀，但不曉得每搜船的分布，再想像一下情境，考慮要摧毀所有船，則投下每個飛彈於船艦位置，因此不用考慮哪個位置是哪艘船。由於有雷達受到阻礙，有些地方無法偵測，現在海上有七艘船，而船的形狀有七種(俄羅斯方塊)，但可以接受旋轉，最多錯失一枚飛彈，而每次丟飛彈時，馬上就會知道有沒有擊中，問有沒有可能藉由「最多錯失一枚飛彈」的條件打到所有的位置。

把所有分配位置求出，窮舉一枚飛彈射錯的地方，那麼如果可行解只有一解，那麼可以將此點移除，反之就是沒射錯，換下一枚。由於可形解會產生交集可能，當剔除一解時，另一個解就會受到釋放，如果每個解最後都因為飛彈射錯而被剔除則是 "yes."，反之則是 "no."。

必須特別考慮唯一解，即不會射錯飛彈。直接輸出 "yes."

由於每一枚錯誤的飛彈只能剔除一解，因此當找到不同配置方式大於 h*w 則是無解情況，因為必然有一解以上會剔除不掉，這是一個很重要的剪枝。
-----
我知道只有土豪會這麼射飛彈，不過題目真的很不好懂，情境想了很久很久沒有著落，請允許這麼描述題目。

必須使用 bitmap 加快速度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
char img[19][4][5] = {// 19 kinds by 4x4
    {{"xx.."},
     {"xx.."},
     {"...."},
     {"...."}},
    {{"xx.."},
     {".xx."},
     {"...."},
     {"...."}},
    {{".x.."},
     {"xx.."},
     {"x..."},
     {"...."}},
    {{".xx."},
     {"xx.."},
     {"...."},
     {"...."}},
    {{"x..."},
     {"xx.."},
     {".x.."},
     {"...."}},
    {{"x..."},
     {"xxx."},
     {"...."},
     {"...."}},
    {{".x.."},
     {".x.."},
     {"xx.."},
     {"...."}},
    {{"xx.."},
     {"x..."},
     {"x..."},
     {"...."}},
    {{"xxx."},
     {"..x."},
     {"...."},
     {"...."}},
    {{"..x."},
     {"xxx."},
     {"...."},
     {"...."}},
    {{"x..."},
     {"x..."},
     {"xx.."},
     {"...."}},
    {{"xx.."},
     {".x.."},
     {".x.."},
     {"...."}},
    {{"xxx."},
     {"x..."},
     {"...."},
     {"...."}},
    {{"xxxx"},
     {"...."},
     {"...."},
     {"...."}},
    {{"x..."},
     {"x..."},
     {"x..."},
     {"x..."}},
    {{".x.."},
     {"xxx."},
     {"...."},
     {"...."}},
    {{"x..."},
     {"xx.."},
     {"x..."},
     {"...."}},
    {{"xxx."},
     {".x.."},
     {"...."},
     {"...."}},
    {{".x.."},
     {"xx.."},
     {".x.."},
     {"...."}}
};
int kinds[19] = {0,1,1,2,2,3,3,3,3,4,4,4,4,5,5,6,6,6,6};
int hk[19] = {2,2,3,2,3,2,3,3,2,2,3,3,2,1,4,2,3,2,3};
int wk[19] = {2,3,2,3,2,3,2,2,3,3,2,2,3,4,1,3,2,3,2};
int lk[7] = {0, 1, 3, 5,  9, 13, 15};
int rk[7] = {0, 2, 4, 8, 12, 14, 18};
int h, w;
char g[30][30];
struct BITMAP {//16x16 = 256, 256/64 = 4
    unsigned long long f[4];
};
BITMAP bitImg[19][16][16];// transform img->bitImg, [kinds][left_upX][left_upY]
#define DEBUG (0)
void buildBitImg() {
    int i, j, k;
    int p, q;
    memset(&bitImg, 0, sizeof(bitImg));
    for(i = 0; i < 19; i++) {
        for(p = 0; p+hk[i] <= 16; p++) {
            for(q = 0; q+wk[i] <= 16; q++) {
                for(j = 0; j < 4; j++) {
                    for(k = 0; k < 4; k++) {
                        if(img[i][j][k] == 'x') {
                            int pos = (p+j)*16+(q+k);
                            bitImg[i][p][q].f[pos/64] |= 1LLU<<(pos%64);
                        }
                    }
                }
#if DEBUG == 2
                for(j = 0; j < 16; j++, puts("")) {
                    for(k = 0; k < 16; k++) {
                        int pos = j*16+k;
                        int v = (bitImg[i][p][q].f[pos/64]>>(pos%64))&1;
                        printf("%d", v);
                    }
                }
                puts("");
                getchar();
#endif
            }
        }
    }
}
void printBITMAP(BITMAP &S) {
    int i, j;
    for(i = 0; i < h; i++, puts("")) {
        for(j = 0; j < w; j++) {
            int pos = i*16+j;
            int v = (S.f[pos/64]>>(pos%64))&1;
            printf("%d", v);
        }
    }
    puts("");
}
BITMAP G, X;
BITMAP buf[1000];
int solution;
int check(BITMAP &Filter, BITMAP &IMG) {
    int i;
    unsigned long long r1, r2;
    r1 = 1, r2 = 0;
    for(i = 0; i < 4; i++) {
        r1 &= (G.f[i]&IMG.f[i]) == IMG.f[i];
        r2 |= Filter.f[i]&IMG.f[i];
    }//r2 == 0 and r1 == 1
    return r1 == 1 && r2 == 0;
}
void dfs(int idx, BITMAP &S, BITMAP &Filter) {//find i-th ship cover map
    // G: (x, y) still can place set 1, i.e. can_used[x][y]
    // Filter: (x, y) is obstacle set 1, i.e. 'o'
    int i, j, k, p, f;
    BITMAP NS;
    if(solution > h*w)  return;
    if(idx == 7) {//find one of solutions
        for(i = 0; i < 4; i++) {//all 'x' must be cover.
            if((S.f[i]&X.f[i]) != X.f[i])
                return;
        }
        for(i = 0; i < solution; i++) {
            for(j = 0; j < 4; j++)
                if(buf[i].f[j] != S.f[j])
                    break;
            if(j == 4)//equal
                return;
        }
        if(solution > h*w)  return;
        for(i = 0; i < 4; i++)
            buf[solution].f[i] = S.f[i];
        solution++;
#if DEBUG == 1
    for(i = 0; i < h; i++, puts("")) {
        for(j = 0; j < w; j++) {
            int pos = i*16+j;
            int v = (S.f[pos/64]>>(pos%64))&1;
            printf("%d", v);
        }
    }
    puts("");
    getchar();
#endif
        return;
    }

    for(i = lk[idx]; i <= rk[idx]; i++) {//this ship rotation
        for(j = 0; j+hk[i] <= h; j++) {
            for(k = 0; k+wk[i] <= w; k++) {
                f = check(Filter, bitImg[i][j][k]);
                if(f == 1) {
                    NS = S;
                    for(p = 0; p < 4; p++) {
                        G.f[p] ^= bitImg[i][j][k].f[p];
                        NS.f[p] |= bitImg[i][j][k].f[p];
                    }
                    dfs(idx+1, NS, Filter);
                    for(p = 0; p < 4; p++) {
                        G.f[p] ^= bitImg[i][j][k].f[p];
                        NS.f[p] |= bitImg[i][j][k].f[p];
                    }
                }
            }
        }
    }
}
int main() {
    buildBitImg();
    /*freopen("in.txt", "r+t", stdin);
	freopen("out2.txt", "w+t", stdout);*/
    int i, j, k, cases = 0;
    while(scanf("%d %d", &w, &h) == 2 && h) {
        for(i = 0; i < h; i++)
            scanf("%s", g[i]);
        BITMAP Filter, S;
        memset(&G, 0, sizeof(G));
        memset(&S, 0, sizeof(S));
        memset(&X, 0, sizeof(X));
        memset(&Filter, 0, sizeof(Filter));
        for(i = 0; i < h; i++) {
            for(j = 0; j < w; j++) {
                int pos = i*16+j;
                if(g[i][j] == 'o')  Filter.f[pos/64] |= 1LLU<<(pos%64);
                else  G.f[pos/64] |= 1LLU<<(pos%64);//'.' or 'x'
                if(g[i][j] == 'x')  X.f[pos/64] |= 1LLU<<(pos%64);
            }
        }
        solution = 0;
        dfs(0, S, Filter);
        printf("Game #%d\n", ++cases);
        if(solution == 0) {
            puts("no.");
        } else {
            int update;
            int judge[10000] = {};
            do {
                update = 0;
                for(i = 0; i < h; i++) {
                    for(j = 0; j < w; j++) {
                        if(g[i][j] != '.')  continue;
                        // if cover '.' -> 'o', must be one solution.
                        int sol = 0, solidx;
                        int pos = i*16+j, v;
                        for(k = 0; k < solution; k++) {
                            if(judge[k])    continue;
                            v = (buf[k].f[pos/64]>>(pos%64))&1;
                            if(v == 0) {// one solution don't place (i, j)
                                sol++, solidx = k;
                                if(sol >= 2)    break;
                            }
                        }
                        if(sol == 1) {
                            judge[solidx] = 1;
                            update = 1;
                        }
                    }
                }
            } while(update);
            int ret = 1;
            for(i = 0; i < solution; i++)
                ret &= judge[i];
            if(solution == 1)   ret = 1;
            puts(ret ? "yes." : "no.");
        }
        puts("");
    }
    return 0;
}