并查集應(yīng)用的變形。題目意思是一個(gè)圖中，只有上下左右四個(gè)方向的邊。給出這樣的一些邊，
求任意指定的2個(gè)節(jié)點(diǎn)之間的距離。
有可能當(dāng)前給出的信息，沒(méi)有涉及到要求的2個(gè)節(jié)點(diǎn)，或者只涉及到了1個(gè)節(jié)點(diǎn)，那么肯定
無(wú)法確定它們的距離。或者根據(jù)已經(jīng)給出的邊只知道這2個(gè)節(jié)點(diǎn)在不同的聯(lián)通分量里面，那么其
距離也是無(wú)法確定的，根據(jù)題目要求，輸出-1。
問(wèn)題是如果能夠確定它們?cè)谝粋€(gè)聯(lián)通分量里面，如何確定它們的距離了。
這個(gè)題的關(guān)鍵在于，只有上下左右四個(gè)方向的邊，假設(shè)每個(gè)節(jié)點(diǎn)都有一個(gè)坐標(biāo)的話，那么它們
相對(duì)于代表該聯(lián)通分量節(jié)點(diǎn)的坐標(biāo)肯定是固定的，那么就不需要考慮圖里面有環(huán)之類的情況了。
這樣就可以很方便的應(yīng)用并查集來(lái)解了。
利用并查集，給每個(gè)節(jié)點(diǎn)附加其它信息，即相對(duì)于代表該并查集的節(jié)點(diǎn)的坐標(biāo)（x，y）。
在FindSet里面求出坐標(biāo)，在UnionSet里面修改合并后新加入的另外一個(gè)集合的根節(jié)點(diǎn)的坐標(biāo)即可。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int MAX_N = 40010;
int nN, nM;
int nSets[MAX_N];
int nX[MAX_N];
int nY[MAX_N];
char szInput[MAX_N][100];
void MakeSets(
int nNum)
{
for (
int i = 0; i < nNum; ++i)
{
nSets[i] = i;
nX[i] = nY[i] = 0;
}
}
int FindSets(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSets(nSets[nI]);
nX[nI] += nX[nPre];
nY[nI] += nY[nPre];
}
return nSets[nI];
}
void UnionSets(
int nBeg,
int nEnd,
int dx,
int dy)
{
int nA = FindSets(nBeg);
int nB = FindSets(nEnd);
if (nA != nB)
{
nSets[nB] = nA;
//把集合B合并到集合A中
nX[nB] = nX[nBeg] + dx - nX[nEnd];
//因?yàn)榉较蚰孢^(guò)來(lái)了,所以是減去
nY[nB] = nY[nBeg] + dy - nY[nEnd];
}
}
int main()
{
int nBeg, nEnd, nL;
char szDir[10];
while (scanf("%d%d%*c", &nN, &nM) == 2)
{
MakeSets(nN);
for (
int i = 0; i < nM; ++i)
{
fgets(szInput[i], 100, stdin);
}
int nK;
int nF1, nF2, nI;
scanf("%d", &nK);
int nCur = 0;
while (nK--)
{
scanf("%d%d%d", &nF1, &nF2, &nI);
for (
int i = nCur; i < nI; ++i)
{
sscanf(szInput[i], "%d%d%d%s", &nBeg,
&nEnd, &nL, szDir);
int dx = 0, dy = 0;
switch (szDir[0])
{
case 'N': dy += nL;
break;
case 'S': dy -= nL;
break;
case 'E': dx += nL;
break;
case 'W': dx -= nL;
break;
}
UnionSets(nBeg, nEnd, dx, dy);
}
nCur = nI;
if (FindSets(nF1) != FindSets(nF2))
{
printf("-1\n");
}
else {
printf("%d\n", abs(nX[nF1] - nX[nF2])
+ abs(nY[nF1] - nY[nF2]));
}
}
}
return 0;
}