#include <bits/stdc++.h>
using namespace std;
const int N = 2005,M = 2e5+15,T = 20;
int color[N][N];
int py[M],px[M];
vector<pair<int,int> >adj[N];
int par[M];
int f(int x){
if(x==par[x])return x;
return par[x]= f(par[x]);
}
bool vis[M];
int dy[4]= {1,-1,0,0},dx[4]= {0,0,1,-1};
int dist(int id,int y,int x){
return abs(py[id]-y)+ abs(px[id]-x);
}
int depth[M],lca[M][T],value[M][T];
void dfs(int root,int p){
depth[root]= depth[p]+1;
vis[root]= 1;
for(int i=1;i<T;++i){
lca[root][i]= lca[lca[root][i-1]][i-1];
value[root][i]= max(value[root][i-1], value[lca[root][i-1]][i-1]);
}
for(int i=0;i<adj[root].size();++i){
int u = adj[root][i].second;
int m = adj[root][i].first;
if(u==p)continue;
lca[u][0]= root;
value[u][0]= m;
dfs(u,root);
}
}
int getvalue(int x,int y){
if(depth[x]<depth[y])swap(x,y);
int D= depth[x]-depth[y];
int val = 0;
for(int i=0;i<T;++i){
if(D&(1<<i)){
val= max(val, value[x][i]);
x = lca[x][i];
}
}
if(x!=y){
for(int i=T-1;i>=0;--i){
if(lca[x][i]!= lca[y][i]){
val = max(val,value[x][i]);
val = max(val,value[y][i]);
x = lca[x][i],y = lca[y][i];
}
}
val = max(val,max(value[x][0],value[y][0]));
}
return val;
}
int main(){
//freopen("input.txt","r",stdin);
int h,w,p,q;
cin>>h>>w>>p>>q;
for(int i=1;i<=h;++i){
string s;cin>>s;
for(int j=1;j<=w;++j){
if(s[j-1]=='#'){
color[i][j]= -1;
}
}
}
int y,x;
queue<pair<pair<int,int>,int> >qq,temp;
for(int i=1;i<=p;++i)
{
par[i]= i;
scanf("%d%d",&py[i],&px[i]);
color[py[i]][px[i]]= i;
qq.push(make_pair(make_pair(py[i],px[i]),i ));
}
while(!qq.empty()){
while(!qq.empty()){
int id= qq.front().second, y = qq.front().first.first, x = qq.front().first.second;
qq.pop();
for(int j=0;j<4;++j){
int ny = dy[j]+ y, nx = dx[j] + x;
if(ny>0 && ny<=h && nx>0 && nx<=w && color[ny][nx]==0){
color[ny][nx]= id;
temp.push(make_pair(make_pair(ny,nx),id));
}
}
}
swap(qq,temp);
}
vector<pair<int,pair<int,int> > >Edge;
for(int i=1;i<=h;++i){
for(int j=1;j<=w;++j){
if(color[i][j]!=-1){
int id = color[i][j];
int id2= color[i][j+1];
if(j+1<=w && id2!=id && id2!=-1 ){
Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i,j+1),make_pair(id,id2)));
}
id2 = color[i+1][j];
if(i+1<= h && id2!=id && id2!=-1){
Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i+1,j),make_pair(id,id2)));
}
}
}
}
sort(Edge.begin(),Edge.end());
for(int i=0;i<(int)Edge.size();++i){
int a = Edge[i].second.first, b = Edge[i].second.second;
if(f(a)!=f(b)){
par[f(b)]= f(a);
//cout<<a<<" "<<b<<" "<<Edge[i].first<<endl;
adj[a].push_back(make_pair(Edge[i].first,b));
adj[b].push_back(make_pair(Edge[i].first,a));
}
}
for(int i=1;i<=p;++i){
if(!vis[i]){
dfs(i,0);
}
}
while(q--){
scanf("%d%d",&x,&y);
if(f(x)!=f(y)){
printf("-1\n");
}
else{
printf("%d\n",getvalue(x,y));
}
}
}
Compilation message
bottle.cpp: In function 'void dfs(int, int)':
bottle.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[root].size();++i){
^
bottle.cpp: In function 'int main()':
bottle.cpp:101:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&py[i],&px[i]);
^
bottle.cpp:169:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
9884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
401 ms |
34752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
