题意分析

游戏规则：

1. 在一个 $N \times M$ 的棋盘上放置若干张卡片（用字母 $A, B, C, D$ 表示，空位用 $*$ 表示）。
2. 玩家需要成对消除相同卡片，且连接它们的路径最多只能转折 $3$ 次（即不超过 $3$ 条线段）。
3. 若最终能清空所有卡片，则输出 yes，否则输出 no。

输入要求：

• 每组测试数据包含棋盘尺寸 $N, M$（$2 \leq N, M \leq 10$）和棋盘布局。
• 输入以 $0\ 0$ 结束。

输出要求：

• 判断当前棋盘是否有解。

解题思路

1. 问题转化：

   • 判断是否存在一种消除顺序，使得所有卡片能按规则两两配对并移除。
   • 核心是搜索可行路径，同时处理连通性问题。

2. 关键观察：

   • 每对卡片必须满足路径转折 $\leq 2$ 次（即 $3$ 条线段）。
   • 路径不能穿过其他卡片（只能走空格 $*$）。

3. 算法选择：

   • DFS/BFS + 回溯：尝试所有可能的消除顺序，并验证每对卡片的连通性。
   • 状态压缩：棋盘状态可用二维数组表示，需高效处理消除后的空格。

实现步骤

1. 预处理棋盘：

   • 统计每种卡片的位置列表（如所有 $A$ 的位置）。
   • 确保每种卡片的数量是偶数（否则直接无解）。

2. 路径检查：

   • 对于每对相同卡片，用 BFS/DFS 检查是否存在合法路径（转折 $\leq 2$ 次）。
   • 路径搜索时需避开其他卡片，仅通过空格 $*$。

3. 回溯消除：

   • 按字典序尝试消除卡片对，递归判断剩余棋盘是否有解。
   • 若某次消除导致后续无解，则回溯尝试其他对。

4. 终止条件：

   • 棋盘为空时返回 yes。
   • 所有尝试均失败后返回 no。

代码实现

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int mp[12][12],n,m,num[5],sum;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool flag,vis[11][11];
char str[12];
void Init()
{
    memset(mp,0,sizeof mp);
    memset(num,0,sizeof num);
    sum = flag = 0;
}
struct Node
{
    int x,y,turn,d;
    Node(){}
    Node(int a,int b,int c,int dd)
    {x = a; y = b; turn = c; d = dd;}
};
bool inarea(int x,int y)
{
    if(x<1||y<1||x>n||y>m) return false;
    else return true;
}
void bfs(int x,int y,int w,Node *can,int &len)
{
    memset(vis,0,sizeof vis);
    queue<Node> Q;
    Q.push(Node(x,y,0,-1));
    vis[x][y] = 1;
    while(!Q.empty())
    {
        Node u = Q.front();
        Q.pop();
        if(mp[u.x][u.y] == w)
        {
            can[++len].x = u.x;
            can[len].y = u.y;
            continue;
        }
        for(int i = 0; i < 4; i++)
        {
            int tx = u.x+dir[i][0],ty = u.y+dir[i][1],tturn = 0;
            if(!inarea(tx,ty) || (mp[tx][ty] != -1&&mp[tx][ty] != w) || vis[tx][ty]) continue;
            if(u.d == i||u.d == -1)
                tturn = u.turn;
            else tturn = u.turn+1;
            if(tturn > 2) continue;
            vis[tx][ty] = 1;
            Q.push(Node(tx,ty,tturn,i));
        }
    }
}
bool check()
{
    for(int i = 1; i < n; i++)
        for(int j = 1; j < m; j++)
        {
            if(mp[i][j] != -1&&mp[i][j+1] != -1&&mp[i][j] != mp[i][j+1])
            {
                if(mp[i][j] == mp[i+1][j+1]&&mp[i][j+1] == mp[i+1][j]&&num[mp[i][j]] == 2&&num[mp[i][j+1]] == 2)
                    return false;
            }
        }
    return true;    
}
void dfs(int cur)
{
    if(cur == 0)
    {
        flag = 1;
        return;
    }
    if(flag) return;
    if(!check()) return;//减枝
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
        if(flag) return;
        if(mp[i][j] != -1)
        {
            int w = mp[i][j],len = 0;
            Node can[110];
            mp[i][j] = -1;
            bfs(i,j,w,can,len);//搜索能与(i,j)配对的牌
            for(int k = 1; k <= len; k++)
            {
                mp[can[k].x][can[k].y] = -1;
                num[w] -= 2;
                dfs(cur-2);
                num[w] += 2;
                mp[can[k].x][can[k].y] = w;
            }
            mp[i][j] = w;
        }
    }   
}
int main()
{
    while(scanf("%d%d",&n,&m) != EOF&&n+m)
    {
        Init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%s",str+1);
            for(int j = 1; j <= m; j++)
            {
                if(str[j] == '*') mp[i][j] = -1;
                else mp[i][j] = str[j]-'A'+1,num[str[j]-'A'+1]++;
            }
        }
        sum = num[1]+num[2]+num[3]+num[4];
        if(num[1]%2||num[2]%2||num[3]%2||num[4]%2)//有的牌只有奇数个，无解
        {   
            printf("no\n");
            continue;
        }
        dfs(sum);
        if(flag) printf("yes\n");
        else printf("no\n");
    }
}