题解：P15647 [ICPC 2022 Tehran R] Magic with Cards

· · 题解

思路

  1. 位置 1 到 2 \cdot n，每次可以选两种变换：

  2. BFS 找从 i 到 j 的最短路径，每个点有两个邻居：r(p) 和 s(p)。
  3. 搜到 j 输出步数，搜不到输出 -1。

::::success[\texttt{AC code}]{open}

#include <bits/stdc++.h>
using namespace std;
int n,i,j,N,a[200005],d[200005],x,y;
queue<int> q;
int main(){
    scanf("%d%d%d",&n,&i,&j);
    N=n*2;
    for(int p=1;p<=n;p++)a[p]=p*2-1;
    for(int p=n+1;p<=N;p++)a[p]=(p-n)*2;
    memset(d,-1,sizeof d);
    d[i]=0,q.push(i);
    while(!q.empty()){
        x=q.front(),q.pop();
        if(x==j){printf("%d\n",d[x]);return 0;}
        y=a[x];
        if(d[y]==-1)d[y]=d[x]+1,q.push(y);
        y=x%2?x+1:x-1;
        if(d[y]==-1)d[y]=d[x]+1,q.push(y);
    }
    printf("-1\n");
    return 0;
}

::::