#include <memory.h>
#include <string>
#include <iostream>

using namespace std;

const int drow[4]={0,1,0,-1};
const int dcol[4]={1,0,-1,0};

int r,c,map[12][12],last[5],ans;

int search(int row,int col);

int main()
{
	while (cin>>r>>c && r>0 && c>0)
	{
		memset(last,0,sizeof(last));
		memset(map,0xFF,sizeof(map));
		
		string s;
		getline(cin,s);
		last[0]=r*c;
		for (int i=1;i<=r;i++)
		{
			getline(cin,s);
			for (int j=0;j<c;j++)
			if (s[j]=='*')
				map[i][j+1]=0;
			else
			{
				map[i][j+1]=s[j]-'A'+1;
				last[map[i][j+1]]++;
				last[0]--;
			}
		}
		
		ans=0;
		for (int i=1;i<=4;i++)	if (last[i]%2==1) ans=2;		
	
		if (ans==0) search(1,1);
		
		if (ans==1) cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	
	return 0;
}

int search(int row,int col)
{
	if (last[0]==r*c)
	{
		ans=1;
		return 0;
	}
	
	int queue[12*12+3][2],visited[12][12],head,tail,jhead,jtail,i,j,p,tr,tc,len,k,kind,level,trow,tcol,cc;
	
	trow=row;
	tcol=col;
	cc=1;
	for (int line=row;line<=r;line++)
	if (cc==1)
	{
		cc=1;
		for (int tt=col;tt<=c;tt++)
			if (map[line][tt]>0) cc=0;
		if (cc==1) trow=line;
	}
	
	cc=1;
	for (int tt=col;tt<=r;tt++)
	if (cc==1)
	{
		cc=1;
		for (int line=row;line<=r;line++)
			if (map[line][tt]>0) cc=0;
		if (cc==1) tcol=tt;
	}
	
	for (i=trow;i<=r;i++)
		for (j=tcol;j<=c;j++)
		if (map[i][j]>0)
		{
			kind=map[i][j];
			
			memset(visited,0,sizeof(visited));
			head=1;
			tail=1;
			visited[i][j]=1;
			queue[1][0]=i;
			queue[1][1]=j;
			level=0;
			
			while (ans==0 && tail>=head && level<3)
			{
				level++;
				jhead=head;
				jtail=tail;
				head=tail+1;
				for (p=jhead;p<=jtail;p++)
				{
					for (k=0;k<4;k++)
					{
						len=1;
						tr=queue[p][0]+len*drow[k];
						tc=queue[p][1]+len*dcol[k];
						while (tr<=r+1 && tc<=c+1 && tr>=0 && tc>=0 && visited[tr][tc]==0 && map[tr][tc]<=0)
						{
							tail++;
							queue[tail][0]=tr;
							queue[tail][1]=tc;
							visited[tr][tc]=1;
							len++;
							tr=queue[p][0]+len*drow[k];
							tc=queue[p][1]+len*dcol[k];
						}
						if (tr<=r+1 && tc<=c+1 && tr>=0 && tc>=0)
							if (map[tr][tc]==kind && visited[tr][tc]==0)
								if (tc>=j)
								{
									visited[tr][tc]=1;
									map[i][j]=0;
									map[tr][tc]=0;
									last[kind]-=2;
									last[0]+=2;
									if (last[0]==r*c) ans=1;
									else if (ans==0) search(trow,tcol);
									last[0]-=2;
									last[kind]+=2;
									map[tr][tc]=kind;
									map[i][j]=kind;
								}
					}
				}
				
				
			}
		}
	
	return 0;
}

• Re:TLE * n !!!!!!! 唉，怎么做啊 (96) fisheatscats 2007-11-02 09:44:33
  • Re:TLE * n !!!!!!! 唉，怎么做啊 (104) tcxhb 2008-11-26 17:50:38