[BZOJ4242] kettle (Kruskal reconstruction tree, BFS)

surface”

BZOJHowever, it is a question of jurisdiction.

Description

JOIThe IOI city where you live is famous for its very hot season all year round.
IOIThe city is a rectangle divided into vertical H * horizontal W blocks, each of which is one of the buildings, fields, and walls. The area of the building is P, numbered 1… P.
JOIYou can only enter buildings and wilderness, and each time you can only walk to adjacent areas, and can not move outside the city.
JOIBecause of all kinds of things, he must travel between buildings. Although the air-conditioning equipment in the building is very good, the daylight on the field is very strong, so it takes one unit of water to walk through each area of the field. Besides, there are no such things as vending machines, drinking water and so on on the field.People in IOI city usually carry a kettle. The size of a x kettle can hold up to X of water. There is tap water in the building to fill the kettle.
Since it was difficult to carry a large kettle, JOI decided to move it as small as possible. Therefore, in order to be able to move between buildings at any time, please help him write a program to calculate the minimum required size of the kettle.
Given the map of the city of IOI and Q queries, the first one (1< = i< = Q) is “What is the minimum size of kettle needed to move between Si and Ti in a building?” Please answer the corresponding answers for each query output.

Input

The integer H, W, P, Q on the first line, divided by four spaces, indicates that the city of IOI is divided into vertical H * horizontal W blocks with P buildings and Q queries.
Next, line H, line I (1 & lt; = I & lt; = H) has a string of length W, each of which is either one of’. ‘or’#’,’.’ means the location is a building or a field,’#’means the location is a wall.
The next P line describes the location of each building in the IOI city. Line I (1< = i< = P) has two spaces separated by the integers Ai and Bi, indicating that the location of the first building is in column Bi of the Ai row. Make sure this location is in the map.
Next, line Q, line I (1 & lt; = I & lt; = Q) has two spaces separated by the integers Si and Ti, indicating that the first question is, “What is the minimum size of kettle needed to move between Si and Ti in a building?”

Output

Output Q line, line I (1 & lt; = I & lt; = Q) an integer representing the minimum size of the kettle needed to move between the building Si and Ti.
If it is not reachable, output -1. In addition, if you do not need to go through the field, you will be able to reach 0 output.

Sample Input

5 5 4 4

…..

..##.

.#…

..#..

…..

1 1

4 2

3 3

2 5

1 2

2 4

1 3

3 4

Sample Output

3

4

4

2

HINT

1<=H<=2000

1<=W<=2000

2<=P<=2*10^5

1<=Q<=2*10^5

1<=Ai<=H(1<=i<=P)

1<=Bi<=W(1<=i<=P)

(Ai,Bi)≠(Aj,Bj)(1<=i<j<=P)

1<=Si<Ti<=P(1<=i<=Q)

\(bfs\)，For each grid, two things are recorded: a record of the distance from the nearest building to its current location, and which building it is.
When you are\(bfs\)When you arrive at a grid, you find that the lattice has been marked by other buildings, so you can connect directly from the nearest building to the nearest building to the lattice.
However, this question card often exists.\(4*2000*2000\)，So open one.\(vector\)Record all possible distances, and then hang all the distances on them.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define mp make_pair
#define fr first
#define sd second
#define MAX 2020
#define pb push_back
#define N 200200
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int H,W,P,Q;
pi p[N];
vector<pi> E[MAX*MAX];
char g[MAX][MAX];
int dis[MAX][MAX],bel[MAX][MAX];
int d[4][2]={1,0,0,1,-1,0,0,-1};
struct Line{int v,next;}e[N<<2];
int h[N<<1],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
void bfs()
{
    queue<pi> Q;
    for(int i=1;i<=P;++i)Q.push(p[i]),bel[p[i].fr][p[i].sd]=i;
    while(!Q.empty())
    {
        pi u=Q.front();Q.pop();
        for(int i=0;i<4;++i)
        {
            pi v=mp(u.fr+d[i][0],u.sd+d[i][1]);
            if(g[v.fr][v.sd]=='#'||v.fr<1||v.fr>H||v.sd<1||v.sd>W)continue;
            if(!bel[v.fr][v.sd])
            {
                Q.push(v);
                bel[v.fr][v.sd]=bel[u.fr][u.sd];
                dis[v.fr][v.sd]=dis[u.fr][u.sd]+1;
            }
            else E[dis[v.fr][v.sd]+dis[u.fr][u.sd]].pb(mp(bel[v.fr][v.sd],bel[u.fr][u.sd]));
        }
    }
}
int f[N<<1];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int CNT,w[N<<1],dep[N<<1];
int fa[22][N<<1];
void dfs(int u)
{
    dep[u]=dep[fa[0][u]]+1;
    for(int i=h[u];i;i=e[i].next)
        dfs(e[i].v);
}
void Kruskal()
{
    for(int i=1;i<=P;++i)f[i]=i;CNT=P;
    for(int i=0;i<=H*W;++i)
        for(int j=0,l=E[i].size();j<l;++j)
        {
            int u=getf(E[i][j].fr),v=getf(E[i][j].sd);
            if(u==v)continue;++CNT;
            f[CNT]=f[u]=f[v]=CNT;w[CNT]=i;
            Add(fa[0][u]=CNT,u);Add(fa[0][v]=CNT,v);
        }
    for(int i=1;i<=21;++i)
        for(int j=1;j<=CNT;++j)
            fa[i][j]=fa[i-1][fa[i-1][j]];
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    for(int i=21;~i;--i)
        if(dep[fa[i][u]]>=dep[v])u=fa[i][u];
    if(u==v)return u;
    for(int i=21;~i;--i)
        if(fa[i][u]!=fa[i][v])
            u=fa[i][u],v=fa[i][v];
    return fa[0][u];
}
int main()
{
    H=read();W=read();P=read();Q=read();
    for(int i=1;i<=H;++i)scanf("%s",g[i]+1);
    for(int i=1;i<=P;++i)p[i].fr=read(),p[i].sd=read();
    bfs();Kruskal();for(int i=CNT;i;--i)if(!dep[i])dfs(i);
    int cnt=0;
    while(Q--)
    {
        ++cnt;
        int u=read(),v=read();
        if(getf(u)!=getf(v))puts("-1");
        else printf("%d\n",w[LCA(u,v)]);
    }
    return 0;
}