Attack on Alpha-Zet

题目描述

Space pirate Captain Krys has recently acquired a map of the artificial and highly secure planet Alpha-Zet which he has been planning to raid for ages. It turns out the whole planet is built on a 2D plane with modules that serve as one room each. There is exactly one module at every pair of integer coordinates and modules are exactly 1 × 1 units big. Every module is bidirectionally connected to at least one adjacent module. Also, for any two modules there exists exactly one path between them. All in all the modules create a rectangular maze without any loops.

Figure A.1: Illustration of Sample Input 2
On the map Captain Krys has marked several modules he wants to visit in exactly the marked order. What he intends to do there is none of your business, but he promises you a fortune if you determine the number of modules he has to walk through along
the route (since there are no loops he will always take the direct route from one marked module to the next). The first marked module indicates where he starts his journey, the last where he wants to finish.

输入

The input consists of:
•one line with two integers h and w (2 ≤ h, w ≤ 1 000) describing the height and the width of the maze.
•h + 1 lines follow, describing the maze in ASCII, each line containing 2 · w + 1 characters.
The description always follows these rules:
–In every row, columns with odd index (starting at index 1) contain either vertical walls or spaces and columns with even index contain either horizontal walls or spaces.
–The first row describes the northern wall of the maze (which always consists only of horizontal walls). Every subsequent row describes a row of modules.
–A module is located at every even column index. Its western and eastern walls are located at the directly neighboring odd column indices respectively, its northern wall is located at the same column index but one row above and its southern wall can be found at its own position. If a wall is missing, the corresponding position contains a space instead.
•After the description of the maze, an integer m (2 ≤ m ≤ 104) is given.
•Each of the following m lines describes a marked module with two integer coordinates x and y (1 ≤ x ≤ h; 1 ≤ y ≤ w). The first pair of coordinates is the start point of the journey, the last pair the end point. Modules may appear multiple times but never twice or more in a row. (1, 1) is the top left module and (h, w) is the bottom right module.
It is guaranteed that the maze itself is enclosed. Furthermore it is guaranteed that exactly one path exists between any two modules.

输出

Output one integer, the number of modules Captain Krys has to travel through if he follows the route in the exact order given in the input.

样例输入

2 6
_ _ _ _ _ _ 
|  _ _ _ _ _|
|_ _ _ _ _ _|
5
1 5
1 1
1 6
1 1
1 5

样例输出

18

树上距离，lca裸题
有空格的输入

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
const int maxm=2005;
char mp[maxn][maxm];
int n,m;
 
struct Edge
{
    int v,next;
}e[maxn*maxm*2];
int head[maxn*maxn],tol;
int dep[maxn*maxn];
int f[maxn*maxn][22];
void add(int u,int v){tol++;e[tol].v=v;e[tol].next=head[u];head[u]=tol;}
void input()
{
    getchar();
    for(int i=0;i<=n;i++){
        gets(mp[i]);
    }
}
int num(int i , int j)
{
    i = i-1;
    j = (j+1)/2;
    return i*m+j;
}
 
void build()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=2*m; j+=2)
        {
            if(mp[i][j+1] != '|')
            {
                add(num(i,j) , num(i,j+2));
                add(num(i,j+2) , num(i,j));
            }
            if(mp[i][j] != '_')
            {
                add(num(i,j) , num(i+1,j));
                add(num(i+1,j) , num(i,j));
            }
        }
    }
}
 
void dfs(ll u,ll fa){//dfs建树
    dep[u]=dep[fa]+1;
    f[u][0]=fa;//初始化每个点的父节点
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v!=fa){
            dfs(v,u);
        }
    }
}
void rmq_init(int k)
{
    for(int j=1;j<=19;j++)
        for(int i=1;i<=k;i++)
           if(f[i][j-1]) f[i][j] = f[f[i][j-1]][j-1];
}
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);//深度深的先处理
    for(int i=19;i>=0;i--){
        if(dep[u]>=dep[v]+(1<<i)){
            u = f[u][i];
        }
    }
    if(u==v){//跳到同一深度判断是否完成
        return u;
    }
    for(int i=19;i>=0;i--){//一起跳
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}
void solve()
{
    ll res=0;int l,r;
    int now,last,tmp;
    int q;scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&l,&r);
        now=num(l,r*2-1);
        if(i!=1){
            tmp=lca(last,now);
            res+=(dep[now]-dep[tmp]+dep[last]-dep[tmp]);
        }
        last=now;
    }
    printf("%lld",res);
}
int main()
{
    scanf("%d%d",&n,&m);
    input();
    build();
    dfs(1,0);
    rmq_init(n*m);
    solve();
    return 0;
}