题意分析

1.问题描述：

$Farmer John$ 的农场有 N 个农场（编号为 1 到 N），通过 M 条道路连接。每条道路有固定的长度和方向（北、南、东、西）。$Farmer Bob$ 会提出 K 次查询，每次查询给出两个农场的编号和一个索引 I，表示在输入数据的前 I 条道路之后，这两个农场之间的曼哈顿距离。如果无法确定距离，则输出 -1。

2.输入格式：

第一行：两个整数 N 和 M，分别表示农场数量和道路数量。 接下来的 M 行：每行描述一条道路，包括四个部分：F1、F2、L 和 D。F1 和 F2 是道路连接的两个农场编号，L 是道路长度，D 是道路方向（N、S、E、W）。 第 M+2 行：一个整数 K，表示查询次数。 接下来的 K 行：每行三个整数 F1、F2 和 I，表示查询的两个农场编号和道路索引。 3.输出格式：

对于每个查询，输出两个农场之间的曼哈顿距离或 -1（如果无法确定）。

解题思路

1.关键点：

曼哈顿距离：两个点 $(x1, y1)$ 和 $(x2, y2)$的曼哈顿距离为 $|x1 - x2| + |y1 - y2|$。 并查集$（Union-Find）$：用于动态维护农场的连通性，并在连通时计算相对坐标。 动态处理道路：根据查询的索引 I，逐步添加道路，直到前 I 条道路都被处理。

2.初始化： 使用并查集维护农场的连通性。 每个农场初始时是自己的父节点，相对坐标为 (0, 0)。 3.处理道路： 对于每条道路，根据方向更新两个农场的相对坐标。 合并两个农场的集合，并调整相对坐标以保持一致性。 4.处理查询： 对于每个查询，逐步添加道路，直到前 I 条道路都被处理。 5.检查两个农场是否连通： 如果连通，计算曼哈顿距离。 如果不连通，输出 -1。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define MAX_N 50010

#define sci(num) scanf("%d",&num)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
#define  MOD 3
int fa[MAX_N], rx[MAX_N],ry[MAX_N];
int N,M,K;
struct que{
    int x,y,d;
    
   
   
    
    char
   
    ch;
} qs[40010];
int Find(int x) {
    if (fa[x] != x) {
        int p = fa[x];
        fa[x] = Find(fa[x]);
        rx[x] += rx[p];
        ry[x] += ry[p];
    }
    return fa[x];
}
void init() {
    for (int i = 0;i <= N;i++) {
        fa[i] = i;
        rx[i] = ry[i] = 0;
    }
}
void Union(int x,int y,int d,
   
   
    
    char
   
    ch) {

    int fx = Find(x);
    int fy = Find(y);
    if (ch == 'E' || ch == 'W') {
        if (fx != fy) {
            rx[fy] = rx[x] - (d + rx[y]);
            ry[fy] = ry[x] - ( ry[y]);
            fa[fy] = fx;
        }
    } else if (ch == 'N' || ch == 'S') {
        if (fx != fy) {
            rx[fy] = rx[x] - ( rx[y]);
            ry[fy] = ry[x] - ( d + ry[y]);
            fa[fy] = fx;
        }
    }
}
int main() {
    sci(N); sci(M);
    init();
    for (int i = 0;i < M;i++) {
        scanf("%d %d %d %c\n",&qs[i].x,&qs[i].y,&qs[i].d,&qs[i].ch);
        if (qs[i].ch == 'W') qs[i].d= -qs[i].d;
        if (qs[i].ch == 'S') qs[i].d = -qs[i].d;
    }
    int now = 0;
    sci(K);
    for (int i = 0;i < K;i++) {
        int x,y,w;
        sci(x); sci(y); sci(w);
        for (;now < w;now++) {
            Union(qs[now].x,qs[now].y,qs[now].d,qs[now].ch);
        }
        int fx = Find(x);
        int fy = Find(y);
        if (fx != fy) {
            printf("-1\n");
        } else {
            printf("%d\n",abs(rx[x] - rx[y]) + abs(ry[x] - ry[y]));
        }
    }

    return 0;
}