The End Dimension#12420

The End Dimension (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

Observations:

Cells that are connected without passing through obstacles form connected components. If both the start and the target are in the same component, no teleportation is needed.
It's never optimal to use more than one teleportation device.

Algorithm:

Label all connected components in the grid with DFS/BFS.
Record which components contain teleportation devices.
Perform a BFS from all teleportation devices simultaneously to compute the minimum distance $d [i] [j]$ from the nearest device to each cell $(i, j)$ .
For each query $(x, y, b, c)$ (x,y,b,c):
- If $(x, y)$ and $(b, c)$ are in the same component, cost $= 0$ .
- Else if both $(x, y)$ and $(b, c)$ are in a component containing a teleportation device, the answer is $d [b] [c]$ (since we can teleport from $(x, y)$ 's component to the closest teleportation device to $(b, c)$ .
- Otherwise, the target is unreachable, cost $= - 1$ .

The total complexity is $O (n \cdot m + q)$ \mathcal{O}(n \cdot m + q).


#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>

using namespace std;

ll n,m,q,mx=3e5,gr;
ll a[510][510],g[510][510],d[510][510];
bool has_tele[250005];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],g[i][j]=0,d[i][j]=1e18;

    gr=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!g[i][j]&&a[i][j]!=1)
            {
                has_tele[gr]=0;
                vector<pll> st;
                st.pb({i,j});
                g[i][j]=gr;
                while(!st.empty())
                {
                    auto [x,y]=st.back();st.pop_back();
                    if(a[x][y]==2) has_tele[gr]=1;
                    for(int k=0;k<4;k++)
                    {
                        int nx=x+dx[k],ny=y+dy[k];
                        if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                            if(!g[nx][ny]&&a[nx][ny]!=1)
                                g[nx][ny]=gr,st.pb({nx,ny});
                    }
                }
                gr++;
            }

    queue<pll> qu;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==2)
                d[i][j]=0,qu.push({i,j});

    while(!qu.empty())
    {
        auto [x,y]=qu.front();qu.pop();
        for(int k=0;k<4;k++)
        {
            int nx=x+dx[k],ny=y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!=1)
                if(d[nx][ny]>d[x][y]+1)
                    d[nx][ny]=d[x][y]+1,qu.push({nx,ny});
        }
    }

    cin>>q;
    while(q--)
    {
        int x,y,b,c;cin>>x>>y>>b>>c;
        if(g[x][y]&&g[x][y]==g[b][c]) cout<<0<<"\n";
        else if(g[x][y]&&has_tele[g[x][y]]&&d[b][c]!=1e18) cout<<d[b][c]<<"\n";
        else cout<<-1<<"\n";
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll T=1;
    cin>>T;
    while(T--) solve();
}