[ZJ][LCA] b237. CSAPC'09 迷宮任務
內容 ：
在一个 n 乘以 m 大小的迷宫当中，你必须依序执行很多项搬东西的任务。每一个任务都有起始点 A 以及终点 B 。 行动的时候如果手上没有搬东西，就不会耗费任何体力，但是如果手上有东西，那么耗费的体力就是以移动「一格」消耗一单位的体力来计算。而所谓移动「一格」 是指从目前迷宫中的位置往东、南、西、北四个方向前进一步的长度。有趣的是，经过你的缜密观察，尽管迷宫内部相当复杂，它一定会遵守「右手定则」，也就是 说，只要摸着右手边的墙壁不断地往前行走，终究可以踏遍迷宫中的每一块空地，并且连所有空地周围看得到的围墙部分都被你摸过了。聪明的你在执行每一个任务 的时候，都会挑选最短路径搬运指定物品。请问执行完所有任务以后你所需要耗费的最少体力总和是多少？
輸入說明
：
输入的第一行包含三个正整数 n, m, Q 。接下来我们用 n 列(rows)每一列以 m 个字元来表示迷宫。迷宫内部标注 '.' 的部份是空地，标记 '#' 的部份是墙。迷宫最外围一定都是墙壁。接下来有 Q 列分别代表 Q 项任务的起点和终点，每一列包含四个整数 x, y, z, w ，代表每一项任务从 (x, y) 出发，并且在 (z, w) 结束。注意到迷宫的编号方式以左上角为 (0, 0) ，右下角为 (n-1, m-1) 。你可以假设输入的所有座标都会是空地的座标。 迷宫里面不会有2x2的空地出现。 (edit: 11/16 10:17am)
輸出說明
：
请输出依序执行完所有任务后所需要耗费的最小体力。
範例輸入
：
10 10 6 ########## #......#.# #####.#..# #####...## ###.#.#.## ###.#.#..# ##...#..## ##.#..#.## #...#....# ########## 1 1 1 1 3 6 1 3 3 6 6 3 2 8 2 5 2 5 2 8 7 4 6 2
範例輸出 ：
30
提示
：
测试资料说明
占总分至少 30% 的测试资料中满足 5<= n, m <=30
占总分至少 40% 的测试资料中满足 0 <= Q <= 500
对于所有的测试资料，满足 5<= n, m <=250, 0 <= Q <= 50000 ，并且答案一定不会超过 2147483647 。
出處
：
由題目藉由兩個條件, 右手定則會經過所有的點, 且摸過所有的點旁邊的牆壁, 由此可知是個樹狀圖,
因此我們可以去利用 LCA 找到最鄰近的共同祖先找到最短路徑。
補充一下, LCA 是利用中序探訪, 找到中間深度最小的祖先。
#include <stdio.h>
#include <vector>
#define maxN 65536
using namespace std;
typedef struct {
int nd, dp;
} ELE;
vector<int> g[maxN];
int lidx[maxN], tidx, M;
ELE tree[maxN<<2], stk[maxN<<1];
void dfs(int nd, int dep, int p) {
if(!lidx[nd])
lidx[nd] = tidx;
stk[tidx].nd = nd, stk[tidx++].dp = dep;
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it == p) continue;
dfs(*it, dep+1, nd);
stk[tidx].nd = nd, stk[tidx++].dp = dep;
}
}
void setTree(int n) {
for(M = 1; M < n+1; M <<= 1);
for(int i = 2*M-1; i > 0; i--) {
if(i >= M)
tree[i] = stk[i-M];
else {
if(tree[i<<1].dp < tree[i<<1|1].dp)
tree[i] = tree[i<<1];
else
tree[i] = tree[i<<1|1];
}
}
}
ELE query(int s, int t) {
static int i;
ELE ans;
ans.dp = 0xfffff;
for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
if(~s&1) {
if(ans.dp > tree[s^1].dp)
ans = tree[s^1];
}
if(t&1) {
if(ans.dp > tree[t^1].dp)
ans = tree[t^1];
}
s >>= 1, t >>= 1;
}
return ans;
}
int main() {
int n, m, q, x, i, j;
int x1, y1, x2, y2;
char mg[255][255] = {};
int gn[255][255] = {};
while(scanf("%d %d %d", &n, &m, &q) == 3) {
int size = 0;
for(i = 0; i < n; i++) {
scanf("%s", mg[i]);
for(j = 0; j < m; j++) {
if(mg[i][j] == '.')
gn[i][j] = ++size;
}
}
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(mg[i][j] != '.')
continue;
if(mg[i+1][j] == '.')
g[gn[i][j]].push_back(gn[i+1][j]);
if(mg[i-1][j] == '.')
g[gn[i][j]].push_back(gn[i-1][j]);
if(mg[i][j+1] == '.')
g[gn[i][j]].push_back(gn[i][j+1]);
if(mg[i][j-1] == '.')
g[gn[i][j]].push_back(gn[i][j-1]);
}
}
tidx = 0;
dfs(1, 0, -1);
setTree(tidx);
ELE ans;
int sum = 0;
while(q--) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
i = lidx[gn[x1][y1]], j = lidx[gn[x2][y2]];
if(i > j)
x = i, i = j, j = x;
ans = query(i, j);
sum += -2*stk[lidx[ans.nd]].dp+stk[i].dp+stk[j].dp;
}
printf("%d\n", sum);
for(i = 0; i <= size; i++)
g[i].clear();
}
return 0;
}