不需要DFS,只需每次贪心找出一个配对个数最少的方块（个数为0的不计）消去即可，用这个代替DFS。
这个方法至少我当前没有找到反例，以下是我的理解：

表达能力不强，的和心里想的有很大出入= =|

若当前找到的最少配对个数为k(为0的不计)：
1° 若k>=2，当前无论如何操作都不会造成死局。
2° 若k=1，如果当前操作造成死局，换一种说法：
 死局大体上无非就是两种情况：
  所有的方块配对个数均为0。
  经过某次操作后，以前配对个数不为0的某个方块变成了0，那么这次操作造成死局。

再换言之，当前k=1的点如果跟i消去，结果造成另一也只能和i配对的方块j失去了配对，这就是有可能造成死局的操作。而如果这种局面存在，无论进行其他任何操作都不能避免，因为i,j都要抢k。

可能会有人问：如果其他的一系列操作不会造成这种局面出现呢？我认为不存在这样的操作。因为按照上面的方法，每次选择的都是不会把好局变成死局的“优操作”，因为找的是最小配对个数的消去。这样一步步走下去，策略就应该是可行的。

证明极不严谨，希望各位有反例可以提出。至少这题是ac了。

赠一组数据：
3 4
ACDA
CABD
BCCA
yes

const
 dx:array[1..4]of integer=(-1,1,0,0);
 dy:array[1..4]of integer=(0,0,-1,1);
 dz:array[1..4]of integer=(1,2,3,4);
var
 a:array[-1..12,-1..12]of longint;
 b:array[1..4]of longint;
 c,d:array[1..4,0..100]of longint;
 q:array[0..1000]of record x,y,dat,dir:longint; end;
 v:array[0..11,0..11,1..4]of longint;
 link:array[0..10,0..10]of boolean;
 n,m,i,j,k,tot,min,mi,mj,mx,my,kx,ky,l,r:longint;
 bool:boolean;
 ch:char;

procedure scanf;
 begin
  fillchar(b,sizeof(b),0);
  fillchar(a,sizeof(a),255);
  for i:=0 to n+1 do begin a[i,0]:=0; a[i,m+1]:=0; end;
  for i:=0 to m+1 do begin a[0,i]:=0; a[n+1,i]:=0; end;
  tot:=0;
  for i:=1 to n do
   begin
    for j:=1 to m do
     begin
      read(ch);
      if ch='*' then a[i,j]:=0 else a[i,j]:=ord(ch)-64;
      if a[i,j]<>0 then
       begin
        k:=a[i,j];
        inc(b[k]);
        c[k,b[k]]:=i;
        d[k,b[k]]:=j;
        inc(tot);
       end;
     end;
    readln;
   end;
 end;

function bfs(sx,sy,z:longint):longint;
 var
  i,j,nx,ny,ndat,ndir:longint;
 begin
  bfs:=0;
  fillchar(v,sizeof(v),127);
  fillchar(link,sizeof(link),0);
  l:=1; r:=4;
  for i:=1 to 4 do
   with q[i] do
    begin
     x:=sx; y:=sy;
     dat:=0; dir:=i;
     v[sx,sy,i]:=0;
    end;
  while l<=r do
   with q[l] do
    begin
     for i:=1 to 4 do
      begin
       nx:=x+dx[i];
       ny:=y+dy[i];
       ndir:=dz[i];
       if ndir<>dir then ndat:=dat+1 else ndat:=dat;
       if ndat>2 then continue;
       if (a[nx,ny]=z)and((nx<>sx)or(ny<>sy)) then link[nx,ny]:=true;
       if (a[nx,ny]=0)and(ndat<v[nx,ny,ndir]) then
        begin
         inc(r);
         q[r].x:=nx; q[r].y:=ny;
         q[r].dat:=ndat; q[r].dir:=ndir;
         v[nx,ny,ndir]:=ndat;
        end;
      end;
     inc(l);
    end;
  for i:=1 to n do
   for j:=1 to m do
    if link[i,j] then
     begin
      inc(bfs);
      kx:=i; ky:=j;
     end;
 end;

begin
 repeat
  readln(n,m);
  if n=0 then exit;
  scanf;
  bool:=true;
  while tot>0 do
   begin
    min:=maxint;
    for i:=1 to 4 do
     for j:=1 to b[i] do
      begin
       if a[c[i,j],d[i,j]]=0 then continue;
       k:=bfs(c[i,j],d[i,j],i);
       if (k<min)and(k<>0) then
        begin min:=k; mi:=c[i,j]; mj:=d[i,j]; mx:=kx; my:=ky; end;
      end;
    if min=maxint then begin bool:=false; break; end;
    a[mi,mj]:=0; a[mx,my]:=0;
    dec(tot,2);
   end;
  if bool then writeln('yes') else writeln('no');
 until false;
end.

• Re:不需要DFS，只需BFS。有一个贪心策略，见内 (58) waterkid 2012-02-25 21:55:17
• Re:不需要DFS，只需BFS。有一个贪心策略，见内 (65) lhs123456 2012-05-17 15:15:36