#include<stdio.h>#include<string.h>#include<iostream>using namespace std;#define LL 20#define X 28 typedef struct pot{ int m; int n; bool is_various; int x; int y; pot() { m=0; n=0; is_various=false; x=0; y=0; }}pot,*pot_link;typedef struct grid{ int r; int c; pot val[LL][LL]; grid() { r=0; c=0; }}grid,*grid_link;char grids[500][LL][LL];int cnt=0;int used_grids[500]={0};char in_grid[LL][LL];grid pot_grid;int W=0,H=0;int R=0,C=0;int cases=0;int x_cnt=0;int o_cnt=0;int i_cnt=0;char patterns[19][10][10]={ { "xx", "xx" }, { "xx", " xx" }, { " x", "xx", "x" }, { " xx", "xx" }, { "x ", "xx", " x" }, { "x", "xxx" }, { "xx", "x", "x" }, { "xxx", " x" }, { " x", " x", "xx" }, { " x ", "xxx" }, { "x", "xx", "x" }, { "xxx", " x" }, { " x", "xx", " x" }, { " x", "xxx" }, { "x", "x", "xx" }, { "xxx", "x" }, { "xx", " x", " x" }, { "xxxx" }, { "x", "x", "x", "x" }};int kind_cnt[7]={1,2,2,4,4,4,2};int kind_ind[7]={0,1,3,5,9,13,17};int insert_grid(){ for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(in_grid[i][j]=='.') {grids[cnt][i][j]='o';} else if(in_grid[i][j]>=0&&in_grid[i][j]<=6) {grids[cnt][i][j]='x';} else {grids[cnt][i][j]=in_grid[i][j];} } } cnt++; if(cnt>=1000) {cnt--;} return(0);}int DFS_kind(int cur){ if(x_cnt>28) {return(0);} if(cnt>R*C) {return(-1);} if(cur>=7) { int x_c=0; for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(in_grid[i][j]=='x'||(in_grid[i][j]>=0&&in_grid[i][j]<=6)) {x_c++;} } } if(x_c==28) { insert_grid(); } } else { for(int k=0;k<=kind_cnt[cur]-1;k++) { int pat_ind=kind_ind[cur]+k; for(int nexti=0;nexti<=R-1;nexti++) { for(int nextj=0;nextj<=C-1;nextj++) { int i=0,j=0; int match_cnt=0; int pre_x[5]={0}; int pre_y[5]={0}; char pre_char[5]={0}; while(i<=4-1&&j<=4-1) { char ch=patterns[pat_ind][i][j]; if(ch!=' ') { if(ch=='x') { if(nexti+i>R-1||nextj+j>C-1) {break;} if(in_grid[nexti+i][nextj+j]=='x'||in_grid[nexti+i][nextj+j]=='.') { if(in_grid[nexti+i][nextj+j]=='.') {x_cnt++;} pre_x[match_cnt]=nexti+i; pre_y[match_cnt]=nextj+j; pre_char[match_cnt]=in_grid[nexti+i][nextj+j]; match_cnt++; in_grid[nexti+i][nextj+j]=cur; } else {break;} } } j++; if(j>4-1) { j=0; i++; } } if(match_cnt==4) { int flag=DFS_kind(cur+1); if(flag==-1) {return(-1);} } for(int ci=0;ci<=match_cnt-1;ci++) {in_grid[pre_x[ci]][pre_y[ci]]=pre_char[ci];if(pre_char[ci]=='.') {x_cnt--;}} } } } } return(0);}int constr_pot(){ for(int c=0;c<=cnt-1;c++) { for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(grids[c][i][j]=='x') {pot_grid.val[i][j].n++;} else {pot_grid.val[i][j].m++;} } } } for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0) {pot_grid.val[i][j].is_various=true;} } } return(0);}int sub_grids(pot min_m,char ch,int cur){ for(int c=0;c<=cnt-1;c++) { if(!used_grids[c]&&grids[c][min_m.x][min_m.y]==ch) { used_grids[c]=cur; for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(grids[c][i][j]=='x') {pot_grid.val[i][j].n--;} else {pot_grid.val[i][j].m--;} if(!(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0)) {pot_grid.val[i][j].is_various=false;} } } } } return(0);}int add_grids(int cur){ for(int c=0;c<=cnt-1;c++) { if(used_grids[c]==cur) { used_grids[c]=0; for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(grids[c][i][j]=='x') {pot_grid.val[i][j].n++;} else {pot_grid.val[i][j].m++;} if(pot_grid.val[i][j].m>0&&pot_grid.val[i][j].n>0) {pot_grid.val[i][j].is_various=true;} } } } } return(0);}int DFS_pot(int cur,int use_o){ if(use_o>=2) {return(0);} pot min_m; int flag=0; int mark=0; min_m.m=1000; for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { if(pot_grid.val[i][j].is_various) { flag=1; if(pot_grid.val[i][j].m<min_m.m) { min_m.m=pot_grid.val[i][j].m; min_m.n=pot_grid.val[i][j].n; min_m.x=i; min_m.y=j; } } } } if(!flag) {return(1);} sub_grids(min_m,'x',cur); mark=DFS_pot(cur+1,use_o+1); if(!mark) {return(0);} add_grids(cur); sub_grids(min_m,'o',cur); mark=DFS_pot(cur+1,use_o); if(!mark) {return(0);} add_grids(cur); return(1);}int main(){ while(scanf("%d%d",&H,&W)!=EOF&&(W+H)>0) { R=H; C=W; cnt=0; x_cnt=o_cnt=i_cnt=0; pot_grid.r=R; pot_grid.c=C; memset(grids,' ',sizeof(grids)); memset(used_grids,0,sizeof(used_grids)); for(int i=0;i<=R-1;i++) { for(int j=0;j<=C-1;j++) { pot_grid.val[i][j].is_various=false; pot_grid.val[i][j].m=pot_grid.val[i][j].n=pot_grid.val[i][j].x=pot_grid.val[i][j].y=0; } } printf("Game #%dn",++cases); for(int i=0;i<=R-1;i++) { scanf("%s",in_grid[i]); for(int j=0;j<=C-1;j++) { switch(in_grid[i][j]) { case 'x': x_cnt++; break; case 'o': o_cnt++; break; case '.': i_cnt++; break; } } } if(x_cnt>28) { printf("no.nn"); continue; } DFS_kind(0); constr_pot(); if(cnt>0&&cnt<=R*C&&DFS_pot(1,0)) printf("yes.nn"); else printf("no.nn"); } return(0);}
