PKU1984（Navigation Nightmare）

这题呢，还好吧，主要是在求相对坐标的时候，有点抽象，不过还是可以理解的，画个坐标对一对就知道了

还有就是，并查集的应用，因为要在某一个查询位置判定该点是否已经知道具体坐标，问题转化为俩点是否属于同一个集合，属于同一个集合，则相对于根节点的坐标都知道了，直接求曼哈顿距离，否则无法求出距离

代码中附带了解释：

#include<stdio.h>
#include<string.h>
#define MAXN 40010
int n,m,k;
struct node
{
	int x,y,f;
}f[MAXN];
struct node1
{
	int a,b,d;
	char ch;
}e[MAXN];
int find(int x)
{
	if(x==f[x].f)
		return f[x].f;
	int t=find(f[x].f);
	f[x].x+=f[f[x].f].x;
	f[x].y+=f[f[x].f].y;
	f[x].f=t;
	return f[x].f;
}//查找根节点，路径压缩，同时因为合并集合的时候，只是将某一个集合的根节点合并到另一个集合，即只修改了根节点的相对坐标
//所以查找根节点的过程，修改节点的相对坐标，注意体会这个递归的过程
void Union(int u,int v,int w,char c)
{
	int a=find(u);
	int b=find(v);
	f[b].f=a;//将集合b并入集合a
	int temp1=f[v].x,temp2=f[v].y;
	switch(c)//这个比较好理解
	{
	case 'E': f[b].x=f[u].x+w;f[b].y=f[u].y;break;
	case 'W': f[b].x=f[u].x-w;f[b].y=f[u].y;break;
	case 'N': f[b].y=f[u].y+w;f[b].x=f[u].x;break;
	case 'S': f[b].y=f[u].y-w;f[b].x=f[u].x;break;
	}
	f[b].x-=temp1;//求的是U 所在集合根节点相对于v的坐标
	f[b].y-=temp2;
}
int abs(int a,int b)
{
	if(a>b)
		return a-b;
	else return b-a;
}
int main()
{
	int i,j,s,a,b;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		f[i].f=i;
		f[i].x=f[i].y=0;
	}
	for(i=1;i<=m;i++)
	{
		getchar();
		scanf("%d %d %d %c",&e[i].a,&e[i].b,&e[i].d,&e[i].ch);
	}
	s=0;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d %d %d",&a,&b,&j);
		while(s<j)//这里因为查询位置是递增的，所以只要s比查询位置小，则继续合并
		{
			s++;
			Union(e[s].a,e[s].b,e[s].d,e[s].ch);
		}
		if(find(a)!=find(b))//不在同一个集合，即某一个节点的具体坐标还不知道
			printf("-1\n");
		else 
			printf("%d\n",(abs(f[a].x,f[b].x)+abs(f[a].y,f[b].y)));//求曼哈顿距离
	}
	return 0;
}