题解归档 - cf362A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf362A
• 本地来源：problems/cf362A/idea.md
• 题目链接：https://codeforces.com/contest/362/problem/A
• 原始标题：cf362A — Two Semiknights Meet

思路

cf362A — Two Semiknights Meet

题意

8×8 棋盘，两枚 semiknight（每次走 (±2,±2) 四方向之一）。# 为坏格：可经过，但不能作为会合点；K 位置本身可会合。问是否存在某好格使两子能同时到达。

做法

semiknight 每步行列各变 2，r+c 奇偶不变；但坏格可能切断连通性，不能只看奇偶。

分别从两枚 K 在整张盘上 BFS（# 也可落脚），检查是否存在 s[r][c]!='#' 且两 BFS 均可达的格子。

验证

样例 + stress.py cf362A -n 500

代码

来源：problems/cf362A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:46:11
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char s[9][9];
ll vis1[9][9],vis2[9][9],q[100][2],hd,tl,dr[4]={-2,-2,2,2},dc[4]={-2,2,-2,2};
void bfs(ll sr,ll sc,ll vis[9][9]){
    ll i,j,nr,nc;
    for(i=1;i<=8;i++) for(j=1;j<=8;j++) vis[i][j]=0;
    hd=0,tl=0;
    q[tl][0]=sr,q[tl][1]=sc,tl++;
    vis[sr][sc]=1;
    while(hd<tl){
        nr=q[hd][0],nc=q[hd][1];
        hd++;
        for(i=0;i<4;i++){
            nr=q[hd-1][0]+dr[i],nc=q[hd-1][1]+dc[i];
            if(nr>=1 and nr<=8 and nc>=1 and nc<=8 and !vis[nr][nc]){
                vis[nr][nc]=1;
                q[tl][0]=nr,q[tl][1]=nc,tl++;
            }
        }
    }
}
int main(){
    ll t,i,j,r,c,r1,c1,r2,c2,pd;
    string tmp;
    cin>>t;
    for(i=0;i<t;i++){
        if(i>0){
            getline(cin,tmp);
            getline(cin,tmp);
        }
        r1=c1=r2=c2=0;
        for(r=1;r<=8;r++){
            cin>>s[r];
            for(c=1;c<=8;c++){
                if(s[r][c]=='K'){
                    if(!r1) r1=r,c1=c;
                    else r2=r,c2=c;
                }
            }
        }
        bfs(r1,c1,vis1);
        bfs(r2,c2,vis2);
        pd=0;
        for(r=1;r<=8;r++)
            for(c=1;c<=8;c++)
                if(s[r][c]!='#' and vis1[r][c] and vis2[r][c])
                    pd=1;
        cout<<(pd?"YES":"NO")<<"\n";
    }
    return 0;
}