在大海中，有 n 座不确定坐标的岛屿。接下来，会陆续发现这些岛屿之间的相对位置关系，在发现的过程中，系统也会询问一些岛屿之间的距离：
若有两岛屿的相对位置关系被发现了，则输入格式为 D a b e，表示岛屿 a 在岛屿b 的 D 方向 e 公里。D 必须是 ESWN 中的一个字母，分别表示东南西北四个方向，输入数据保证不会有矛盾的情况发生，但有些信息可能是重复多余的。
如果输入格式为 ? a b，表示需要查询岛屿 a 在岛屿 b 之间的距离。如果 a 与 b 之间的相对关系尚不确定，则输出 ?。
注意，在计算距离时，所使用的定义是横纵坐标的差的绝对值之和，这种距离定义被称为城市距离或曼哈顿距离，而非常用的欧几里得距离。
输入格式
第一行：两个整数 n 与 m；
接下来 m 行：每行首先有一个字母代表操作的类型，接下来有两个整数表示操作涉及的两座岛屿编号 a 与 b：
如果字母是 ‘?’，表示一条查询，输出 a与 b 之间的距离，若它们之间的距离尚不能确定，则输出 ?；
如果字母是 ‘ESWN’ 中的一个，表示这是一条提供岛屿之间相对位置的消息，这一行除 a 与 b 外，最后还有一个正整数 e，表示在 a 的指定方向上与 b 相隔 e 个单位。
这道题第一个小点就是，输入的如果是表示方位的ESWN，那么后面就要有三个输入量，a、b、e；如果输入的是'?' ，那么后面是a、b两个输入的变量；
1）如为？：判断一下岛屿a、b是否在同一集合：find(a)==find(b) && find(a+n)==find(b+n)
是则可以计算出两岛屿的曼哈顿距离为 |dis[a]-dis[b]|+|dis[a+n]-dis[b+n]|，否则输出“?”
（2）如为(D,a,b,e)，则按X轴、Y轴参照方向来合并集合更新代表元、并更新dis[fa[a]]
dis[i]表示i到其祖先的距离
E：东方向，a连b，y为0，所以是 S，是：南方向，x上是0
connect(a,b,e); connect(a+n,b+n,e);
connect(a+n,b+n,0); connect(a,b,0);
W:西方向，b连a，
connect(b,a,e);
connect(a+n,b+n,0);
?:查询，如果x、y都在一个联通块，那么就能计算曼哈顿距离。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int fa[maxn],n,m,dis[maxn];
int find(int x){
if (fa[x]==x) return x;
int fx=find(fa[x]);
dis[x]+=dis[fa[x]];
return fa[x]=fx;
}
inline void connect(int a,int b,int d){
int ra=find(a),rb=find(b);
if (ra==rb) return;
dis[ra]=d-dis[a]+dis[b];
fa[ra]=rb;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=(n<<1);i++)
fa[i]=i;
while(m--){
char opt;
cin>>opt;
switch (opt){
case 'E':
{
int a,b,e;
cin>>a>>b>>e;
connect(a,b,e);
connect(a+n,b+n,0);
break;
}
case 'S':
{ int a,b,e;
cin>>a>>b>>e;
connect(a+n,b+n,e);
connect(a,b,0);
break;
}
case'W':
{int a,b,e;
cin>>a>>b>>e;
connect(b,a,e);
connect(a+n,b+n,0);
break;
}
case 'N':
{
int a,b,e;
cin>>a>>b>>e;
connect(b+n,a+n,e);
connect(a,b,0);
break;
}
case '?':
{
int a,b;
cin>>a>>b;
if (find(a)==find(b)&&find(a+n)==find(b+n)){
cout<<abs(dis[a]-dis[b])+abs(dis[a+n]-dis[b+n])<<'\n';
}else{
cout<<"?\n";
}
}
}
}
return 0;
}
