Miku's Concert#12334

Miku's Concert (Editorial)

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

For each flat cell $(i, j)$ , we precompute the horizontal interval in its row that can be reached without crossing a hill. Let $l [i] [j]$ l[i][j] be the leftmost column reachable from $(i, j)$ in row $i$ , and $r [i] [j]$ r[i][j] be the rightmost one. These values are computed by scanning each row from left to right and from right to left. Thus, while staying in the same row, cell $(i, j)$ can move to any column in

[l [i] [j], r [i] [j]] .

[l[i][j],\ r[i][j]].

Since the movement graph is undirected (if we can move from $(i, j)$ to $(x, y)$ then we can also move from $(x, y)$ to $(i, j)$ ), we run a BFS starting from the concert cell $(n_{1}, m_{1})$ (n_1,m_1). Let $ans [i] [j]$ \text{ans}[i][j] denote the minimum number of moves needed to reach the concert from $(i, j)$ . For each row $i$ , we maintain a set containing all unvisited columns in that row.

When processing a BFS state $(x, y)$ , we first process row $x$ itself. Every unvisited cell in columns $[l [x] [y], r [x] [y]]$ [l[x][y], r[x][y]] can be reached in one move, so we assign them distance $ans [x] [y] + 1$ \text{ans}[x][y]+1 and push them into the BFS queue.

Then we expand upward. For rows $i = x + 1, x + 2, \dots$ i = x+1, x+2, \dots, as long as cell $(i, y)$ is flat and either unvisited or has strictly larger distance than $ans [x] [y]$ \text{ans}[x][y], we maintain the intersection

[l, r] = [l, r] \cap [l [i] [y], r [i] [y]] .

[l,r] = [l,r] \cap [l[i][y], r[i][y]].

All unvisited cells in row $i$ whose columns lie in this interval are reachable in one move and are added to the BFS queue with distance $ans [x] [y] + 1$ \text{ans}[x][y]+1. The same process is applied symmetrically downward for rows $i = x - 1, x - 2, \dots$ i = x-1, x-2, \dots.

Once a cell is visited, it is removed from its row set and will never be processed again.

To see why it is correct to stop the vertical expansion once we encounter a cell $(i, y)$ with

ans [i] [y] \leq ans [x] [y],

\text{ans}[i][y] \le \text{ans}[x][y],

fix a column $y$ and consider one connected vertical segment of flat cells. Inside such a segment, distances can take only two consecutive values, $d$ or $d + 1$ d+1, because if one cell is reachable in $d$ moves, any other cell in the same segment can be reached in at most one additional move. Therefore, once we reach a row with distance not greater than $ans [x] [y]$ \text{ans}[x][y], going further in that direction cannot produce any new cell with a better distance, since it would always be optimal to reach those cells from the already better or equal state.

This also guarantees efficiency. Cells with distance $d + 1$ d+1 never expand vertically, and cells with distance $d$ only expand until they meet another cell with distance $d$ . Hence, each cell in a vertical segment is involved in vertical expansion at most twice. Combined with the logarithmic cost of set operations.

The total complexity is $O (n \cdot m \cdot lo g m)$ O(n \cdot m \cdot \log m)

Implementation

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define pint pair<int,int>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

mt19937 rnd(time(0));

const ll N = 1e6+9;

ll n,m,n1,m1;
vector<bool> a[N];
vector<int> ans[N],l[N],r[N];
queue<pint> q;
set<int> s[N];

void sweep(int i , int l1 , int r1 , int dis)
{
    auto it = s[i].lower_bound(l1);
    while(it!=s[i].end()&&*it<=r1)
    {
        ll j = *it;
        ans[i][j]=dis;
        q.push({i,j});
        it++;
        s[i].erase(s[i].find(j));
    }
}

void bfs(int x , int y)
{
    int l1 = l[x][y] , r1 = r[x][y];
    sweep(x,l1,r1,ans[x][y]+1);
    for(int i = x+1 ; n>=i ; i++)
    {
        if(a[i][y]||(ans[i][y]!=-1&&ans[i][y]<=ans[x][y]))
            break;
        l1=max(l1,l[i][y]);
        r1=min(r1,r[i][y]);
        sweep(i,l1,r1,ans[x][y]+1);
    }
    l1=l[x][y];
    r1=r[x][y];
    for(int i = x-1 ; i>0 ; i--)
    {
        if(a[i][y]||(ans[i][y]!=-1&&ans[i][y]<=ans[x][y]))
            break;
        l1=max(l1,l[i][y]);
        r1=min(r1,r[i][y]);
        sweep(i,l1,r1,ans[x][y]+1);
    }
}

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        cin >> n >> m >> n1 >> m1;
        for(int i = 1 ; n>=i ; i++)
        {
            s[i].clear();
            a[i].clear();
            ans[i].clear();
            l[i].clear();
            r[i].clear();
            a[i].pb(0);
            ans[i].pb(0);
            l[i].pb(0);
            r[i].pb(0);
            for(int j = 1 ; m>=j ; j++)
            {
                bool x;
                cin >> x;
                a[i].pb(x);
                ans[i].pb(-1);
                l[i].pb(0);
                r[i].pb(0);
                s[i].in(j);
            }
        }
        for(int i = 1 ; n>=i ; i++)
        {
            int lst = 0;
            for(int j = 1 ; m>=j ; j++)
            {
                if(a[i][j])
                    lst=j;
                else
                    l[i][j]=lst+1;
            }
        }
        for(int i = 1 ; n>=i ; i++)
        {
            int lst = m+1;
            for(int j = m ; j>0 ; j--)
            {
                if(a[i][j])
                    lst=j;
                else
                    r[i][j]=lst-1;
            }
        }
        while(!q.empty())
            q.pop();
        q.push({n1,m1});
        ans[n1][m1]=0;
        s[n1].erase(m1);
        while(!q.empty())
        {
            ll i = q.front().F;
            ll j = q.front().S;
            q.pop();
            bfs(i,j);
        }
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cout << ans[i][j] << " ";
            lin
        }
    }
}