乡（虚点）
给出一个由ABCD和.组成的字符串。从一个ABCD能跳到另一个ABCD上，同时能从一个字母移动到另一个字母。多次询问从一个字符到另一个字符要走几步？
可以发现，对于一个询问，我们有两种策略：直接暴力走到目的地，或者通过ABCD跳跃。
如果我们选择进行跳跃，那么我们就不用考虑点的确切位置，只需要考虑点是不是在相同字符区间的边界上。
建四个虚点ABCD表示跳跃，然后建图即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn=1e5+5;
int n, Q, p[4];
char s[maxn];
struct Edge{int to, nxt, v;
}e1[maxn*4], e2[maxn*4];
int cnte1, fir1[maxn], cnte2, fir2[maxn];
void addedge(int x, int y, int w, Edge *e, int *fir, int &cnte){Edge &ed=e[++cnte];ed.to=y; ed.nxt=fir[x]; ed.v=w; fir[x]=cnte; }//1:从ABCD到某个点 2:从某个点到ABCD
int dis1[4][maxn], dis2[4][maxn], q[maxn*100], h, t;
void spfa(int src, int *dis, Edge *e, int *fir){memset(dis, 0x3f3f, maxn*4); dis[src]=h=t=0;q[t++]=src; int u, v;while (h<t){u=q[h++];for (int i=fir[u]; i; i=e[i].nxt){v=e[i].to;if (dis[u]+e[i].v<dis[v])dis[v]=dis[u]+e[i].v, q[t++]=v;}}
}int abs(int x){ return x<0?-x:x; }int main(){scanf("%d%d%s", &n, &Q, s+1); int a, b;for (int i=0; i<4; ++i) p[i]=n+i+1;for (int i=1; i<=n; ++i){if (i!=n){ addedge(i, i+1, 1, e1, fir1, cnte1); addedge(i+1, i, 1, e1, fir1, cnte1); addedge(i, i+1, 1, e2, fir2, cnte2); addedge(i+1, i, 1, e2, fir2, cnte2); }if (s[i]=='.') continue;addedge(i, p[s[i]-'A'], 0, e1, fir1, cnte1);addedge(p[s[i]-'A'], i, 1, e1, fir1, cnte1);addedge(p[s[i]-'A'], i, 0, e2, fir2, cnte2);}for (int i=0; i<4; ++i) spfa(p[i], dis1[i], e1, fir1);for (int i=0; i<4; ++i) spfa(p[i], dis2[i], e2, fir2);int ans;for (int i=0; i<Q; ++i){scanf("%d%d", &a, &b); ans=1e9;for (int i=0; i<4; ++i) ans=min(ans, dis1[i][a]+dis2[i][b]);printf("%d\n", min(abs(b-a), ans));}return 0;
}