题解：B4186 [中山市赛 2024/科大国创杯小学组 2023] 六形棋/海克斯

· · 题解

Background

算法：广度优先搜索。

几乎是广搜模板题，没有任何别的什么处理。

至于题目的六边形设定，直接把六个边对应的邻点当做可以扩展的位置，然后当做矩形做即可。

Solution

  1. 先存图，然后依次遍历第一行、第一列，若找到对应人的棋子，就以这个起点开始广搜。

  2. 广搜扩展时，若当前格子为自己的棋子，那么可以更新，入队；否则当做障碍，不可更新，跳过。

  3. 对于每个从队列里面取出的点，直接看是否到了对应的边界，若到了直接返回结果即可，因为题中说了结果唯一。

Code

细节可以看代码。

由于范围不大，直接写临时变量，省的忘记清空。

扩展中的坐标加减情况写常量数组。

#include<bits/stdc++.h>
#define N 105
using namespace std;

class Quick_IO
{
  public:
    template<typename T>
    void read(T &r)
    {
        T x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        r = x * f;
    }
    template<typename T, typename... Args>
    void read(T &tmp, Args &... tmps)
    {
        read(tmp);
        read(tmps...);
    }
} io;

const int mx[7] = {0, 0, 0, 1, 1, -1, -1};
const int my[7] = {0, 1, -1, 0, -1, 0, 1};
int G[N][N];
int T, n;
struct node
{
    int x, y;
};

bool INRANGE(int x, int y)
{
    return (x >= 1 && y >= 1 && x <= n && y <= n);
}

bool BFS(int sx, int sy, bool is_Jimmy) //起始位置，是否是吉米
{
    bool vis[N][N] = {};    //由于范围不大，直接写临时变量，省的清空
    queue<node> Q;
    Q.push({sx, sy});
    vis[sx][sy] = 1;    //标记走过

    while (Q.size())    //BFS
    {
        int ux = Q.front().x, uy = Q.front().y;
        Q.pop();

        if (is_Jimmy && ux == n) return 1;  //检查是否到终点
        if (!is_Jimmy && uy == n) return 1;

        for (int i = 1, vx, vy; i <= 6; i++)
        {
            vx = ux + mx[i], vy = uy + my[i];
            if (!vis[vx][vy] && G[vx][vy] == (is_Jimmy ? 1 : -1) && INRANGE(vx, vy))
            {
                vis[vx][vy] = 1;
                Q.push({vx, vy});
            }
        }
    }
    return 0;
}

string Solve()  //每一轮的处理
{
    for (int i = 1; i <= n; i++)
    {
        if (G[1][i] == 1) if (BFS(1, i, 1)) return "Jimmy";
        if (G[i][1] == -1) if (BFS(i, 1, 0)) return "Chen";
    }
    return "yet";
}

signed main()
{
    io.read(T);
    while (T--)
    {
        memset(G, 0, sizeof G); //多测清空
        io.read(n);
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) io.read(G[i][j]);
        cout << Solve() << "\n";
    }
}