题意分析

• 游戏使用 $4 \times 4$ 的方形棋盘，共 $16$ 个格子。

• 初始布局包含 $4$ 颗黑子（$b$）和 $4$ 颗白子（$w$），其余为空位（$*$）。

• 玩家必须交替移动白子和黑子，第一步必须移动白子。

• 每次移动时，棋子可以沿8个方向（水平、垂直、对角线）滑动，直到：

  • 碰到棋盘边界
  • 碰到其他棋子（无论颜色）

• 禁止跳跃或吃子，且必须移动当前轮次对应颜色的棋子。

• 通过最少步数将初始布局转变为目标布局。

• 若无法达成目标，返回 $-1$。

输入输出要求

• 输入格式

  • 第一行为测试用例数 $w$（$w \leq 6$）。
  • 每个测试用例包含 $8$ 行：
    • 前 $4$ 行：初始棋盘布局
    • 后 $4$ 行：目标棋盘布局
  • 每行 $4$ 个字符（$b$、$w$ 或 $*$）。

• 输出格式

  • 对每个测试用例，输出达成目标的最少步数；若不可达，输出 $-1$。

解题思路

关键问题

1. 状态空间爆炸

   • 棋盘状态数为组合数 $C(16,8)$（选择 $8$ 个位置放置棋子）乘以排列方式，直接暴力搜索不可行。

2. 移动的合法性验证

   • 每次移动需确保：
     • 当前轮次颜色正确（白/黑交替）。
     • 滑动路径无障碍（直到边界或其他棋子）。

3. 最优性要求

   • 需要找到最少步数的解，需采用能保证最优性的算法。

注意事项

• 颜色交替：必须严格遵循白→黑→白的顺序。
• 无解判断：若BFS完成所有可能状态仍未找到目标，返回 $-1$。
• 性能瓶颈：需优化状态存储（如位压缩）以处理较大状态空间。

标程

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int zl[8][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const char now[2]={'w', 'b'};

char op[20];

inline bool in(int x, int y)
{
    return x>=0 && y>=0 && x<4 && y<4;
}

bool dfs(char *s, int step, int deep, int turn)
{
    if(step==deep)
    {
        if(strcmp(s, op)==0) return true;
        return false;
    }
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
        {
            if(s[i*4+j]!=now[turn]) continue;
            for(int k=0; k<8; k++)
            {
                int x=i, y=j;
                for(; in(x+zl[k][0], y+zl[k][1]) && s[(x+zl[k][0])*4+y+zl[k][1]]=='*'; x+=zl[k][0], y+=zl[k][1]);
                s[x*4+y]=now[turn], s[i*4+j]='*';
                if(dfs(s, step+1, deep, 1-turn)) return true;
                s[x*4+y]='*', s[i*4+j]=now[turn];
            }
        }
    return false;
}

int main()
{
    int t; 
    scanf("%d", &t);
    while(t--)
    {
        char s[20];
        // 手动将 s 数组初始化为 0
        for (int i = 0; i < 20; ++i) {
            s[i] = 0;
        }

        // 手动将 op 数组初始化为 0
        for (int i = 0; i < 20; ++i) {
            op[i] = 0;
        }

        for(int i=0; i<4; i++)
            scanf("%s", s+i*4);
        for(int i=0; i<4; i++)
            scanf("%s", op+i*4);
        for(int i=1; ; i++)
            if(dfs(s, 0, i, 0))
            {
                printf("%d\n", i);
                break;
            }
    }
    return 0;
}