gym 101173H

发表于 | 分类于

图转树+LCA


题意

给一个n*n的方格图，’#’表示障碍，’.’表示空地，问点(x1,y1)到点(x2,y2)能够支持平行移动过去的最大方块的大小（要求方块为奇数，移动过程中方块不能越界或者碰到障碍）。

  • n<=1000
  • q<=300000

题解

  • 先对每个空格求出以它为中心可以产生的最大边长d的正方形，然后把每个点坐标(i,j)看成一个新点i×n+j，每个点的权值是d[i][j].
  • 把所有点按照权值从大到小排序。考虑把点生成树，而且树从底向上权值依次减小，每个点找它上下左右四个方向的连通块（已经加进树中）的最小权值点，把这个点的父亲赋为当前点，这样子询问就变成了求树上的LCA，判断点的连通性用并查集即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
char s[maxn][maxn];
int match[maxn][maxn],sum[maxn][maxn];
int n;
struct node {
    int x,y,z;
    bool operator <(const node &rhs)const {
        return z>rhs.z;
    }
} v[maxn*maxn];
int fa[maxn*maxn];
bool vis[maxn][maxn];
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
vector<int> g[maxn*maxn];
int ver[2*maxn*maxn],id[2*maxn*maxn],first[maxn*maxn];
int tot;
int dp[2*maxn*maxn][30];
void dfs(int root,int dep) {
    ver[++tot]=root;
    id[tot]=dep;
    first[root]=tot;
    for(int i=0; i<g[root].size(); i++) {
        int v=g[root][i];
        dfs(v,dep+1);
        ver[++tot]=root;
        id[tot]=dep;
    }
}
void ST() {
    for(int i=1; i<=tot; i++)
        dp[i][0]=i;
    for(int j=1; (1<<j)<=tot; j++) {
        for(int i=1; i+(1<<j)-1<=tot; i++) {
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            dp[i][j]=id[a]<id[b]?a:b;
        }
    }
}
int RMQ(int le,int ri) {
    le=first[le],ri=first[ri];
    if(le>ri) swap(le,ri);
    int k=0;
    while((1<<(k+1))<=ri-le+1) k++;
    int a=dp[le][k],b=dp[ri-(1<<k)+1][k];
    return id[a]<id[b]?ver[a]:ver[b];
}
int find(int x) {
//    printf("%d %d\n",x,fa[x]);
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int init() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='#');
        }
    }
    for(int k=3; k<=n; k+=2) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(match[i][j]>=k-2&&match[i-1][j-1]>=k-2&&match[i-1][j+1]>=k-2
                        &&match[i+1][j-1]>=k-2&&match[i+1][j+1]>=k-2
                        &&match[i-1][j]>=k-2&&match[i+1][j]>=k-2
                        &&match[i][j-1]>=k-2&&match[i][j+1]>=k-2) match[i][j]=k;
            }
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            int p=(i-1)*n+j-1;
            v[p]=(node) {
                i-1,j-1,match[i][j]
            };
            fa[p]=p;
            g[p].clear();
            vis[i-1][j-1]=false;
        }
    }
    sort(v,v+n*n);
//    for(int i=0;i<n*n;i++)
//        printf("%d %d %d\n",v[i].x,v[i].y,v[i].z);
    for(int i=0; i<n*n; i++) {
        int x=v[i].x,y=v[i].y,z=v[i].z;
        vis[x][y]=true;
        for(int j=0; j<4; j++) {
            int nx=x+dir[j][0],ny=y+dir[j][1];
            if(nx<0||ny<0||ny>=n||nx>=n||!vis[nx][ny]) continue;
            int fn=find(nx*n+ny);
            if(fn==find(x*n+y)) continue;
            g[x*n+y].push_back(fn);
//            printf("--%d %d\n",x*n+y,fn);
            fa[fn]=x*n+y;
        }
    }
    return v[n*n-1].x*n+v[n*n-1].y;
}
int main() {
    while(scanf("%d",&n)!=EOF) {
        for(int i=1; i<=n; i++){
            scanf("%s",s[i]+1);
            for(int j=1;j<=n;j++){
                if(s[i][j]=='#') match[i][j]=0;
                else match[i][j]=1;
            }
        }
        int root=init();
        tot=0;
        dfs(root,1);
        ST();
        int q;
        scanf("%d",&q);
        while(q--) {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int r1=(x1-1)*n+y1-1;
            int r2=(x2-1)*n+y2-1;
            root=RMQ(r1,r2);
//            printf("%d %d %d\n",r1,r2,root);
            printf("%d\n",match[root/n+1][root%n+1]);
        }
    }
    return 0;
}
/*
7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7
*/