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

· · 题解

题意：

给你一个 n \times n 的矩阵，如果 Jimmy 已经从第一行走到了第 n 行则输出 Jimmy，如果 Chen 已经从第一列走到了第 n 列则输出 Chen，如果都不成立则输出 yet。

思路：

这题本质就是一个连通块问题，但是本题的方向数组有 6 个。先遍历第 1 行，有 1 就 BFS，再遍历第 1 列，有 -1 就 BFS。

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=105;
int a[N][N];
int t,n;
int dx[6]={0,0,1,1,-1,-1};
int dy[6]={1,-1,0,-1,0,1};
bool vis[N][N];
bool f;
struct node{
    int x,y;
};
bool bfs(int x,int y,int d){
    memset(vis,0,sizeof(vis));
    queue<node>q;
    q.push(node{x,y});
    vis[x][y]=1;
    while(!q.empty()){
        node u=q.front();
        q.pop();
        if((d==-1&&u.y==n)||(d==1&&u.x==n)) return 1;
        for(int i=0;i<6;i++){
            int bx=u.x+dx[i],by=u.y+dy[i];
            if(vis[bx][by]||bx<1||by<1||bx>n||by>n||a[bx][by]!=d) continue;
            vis[bx][by]=1;
            q.push(node{bx,by});
        } 
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) cin>>a[i][j];
        f=0;
        for(int i=1;i<=n;i++){
            if(a[1][i]==1&&bfs(1,i,1)){
                cout<<"Jimmy"<<endl;
                f=1;
                break;
            }
            //(1,i)存在1,那么判断Jimmy是否联通 
        }
        if(f==1) continue;
        for(int i=1;i<=n;i++){
            if(a[i][1]==-1&&bfs(i,1,-1)){
                cout<<"Chen"<<endl;
                f=1;
                break;
            }
            //(i,1)存在-1,那么判断Chen是否联通 
        }
        if(f==1) continue;
        cout<<"yet"<<endl;
    }
    return 0;
}