#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N=14; int n,m,num[6]; int a[N][N]; char c; int flag; int dirx[4]={0,1,0,-1}, diry[4]={1,0,-1,0}; int vis[N][N]; struct Node{ int x,y,dir,trun; Node(int x,int y,int dir,int trun):x(x),y(y),dir(dir),trun(trun){ }; }; bool in(int x,int y){ return x>=0&&x<n&&y>=0&&y<m; } bool cant(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(!in(i+1,j+1)) continue; if(!a[i][j]||!a[i][j+1]) continue; if(a[i][j]&&a[i+1][j]&&a[i][j]==a[i+1][j+1]&&a[i+1][j]==a[i][j+1]&&num[a[i][j]]==2&&num[a[i+1][j]]==2) return true; // 正方形对角线同&&相关的两个颜色块数目就剩正方形里的两个 } } return false; } void bfs(int x,int y,int color,int sam[42][2],int &samn){ queue<Node> q; memset(vis,0,sizeof(vis)); Node f(x,y,-1,0); q.push(f); vis[x][y]=1; while(!q.empty()){ f=q.front(); q.pop(); for(int i=0;i<4;i++){ int nx=f.x+dirx[i], ny=f.y+diry[i], ntrun=f.trun; if(!in(nx,ny)||vis[nx][ny]||(a[nx][ny]!=color&&a[nx][ny]!=0)) continue; //next不在范围内|| 已经访问过||(next颜色与现循环颜色块不符&&next不是空块) if(f.dir!=i&&f.dir!=-1) ntrun+=+1; //方向不同&&不是第一次 if(ntrun>2) continue; //转弯超 vis[nx][ny]=1; if(a[nx][ny]==color){ sam[samn][0]=nx; sam[samn][1]=ny; samn++; continue; } //sam记录相同块坐标 q.push(Node(nx,ny,i,ntrun)); } } } void dfs(int cnt){ if(flag) return; if(cnt==0){ flag=1;return; } if(cant()) return;//cant必须放这里 原来放在main里这个是不对的可能出现: //A*** //*AB* //*BA* //***A //但这里要排除:只剩下: //*** //AB* //BA*这个发生在过程中 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(flag) return; if(!a[i][j]) continue;//空块下一个 int sam[42][2];//记录相同块的坐标,转三个弯最多30 int samn=0,nowcolor=a[i][j]; bfs(i,j,nowcolor,sam,samn);//第ij个,颜色,现在同色的个数 a[i][j]=0; num[nowcolor]-=2; //与下方配合假设消掉 for(int k=0;k<samn;k++){ int x=sam[k][0], y=sam[k][1]; a[x][y]=0;//假设消掉 dfs(cnt-2);//假设消掉 a[x][y]=nowcolor;//还原现场 } a[i][j]=nowcolor;//还原现场 num[nowcolor]+=2; } } } int main(int argc, char** argv) { int cnt; while(scanf("%d%d",&n,&m)==2&&n+m){ flag=0;//是否可以消光 cnt=0;//目前剩下的还要消的颜色块 memset(num,0,sizeof(num));//num记录每种块的数量包括空块 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>c; if(c=='*') num[0]++,a[i][j]=0;//空块不要消 else if(c=='A') num[1]++,a[i][j]=1,cnt++; else if(c=='B') num[2]++,a[i][j]=2,cnt++; else if(c=='C') num[3]++,a[i][j]=3,cnt++; else if(c=='D') num[4]++,a[i][j]=4,cnt++; } } if(num[1]&1||num[2]&1||num[3]&1||num[4]&1){//颜色块否单一定消不掉 printf("no\n"); continue; } dfs(cnt); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }