Mikunun Konserti#12334

Mikunun Konserti (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Hər bir düz hüceyrə $(i, j)$ üçün, biz onun sətirindəki təpəni keçmədən çatmaq mümkün olan üfüqi intervalları əvvəlcədən hesablayırıq. $l [i] [j]$ l[i][j] $(i, j)$ hüceyrəsindən $i$ sətirində çatmaq mümkün olan ən sol sütunu, $r [i] [j]$ r[i][j] isə ən sağ sütunu göstərir. Bu dəyərlər hər bir sətiri soldan sağa və sağdan sola skan edərək hesablanır. Beləliklə, eyni sətirdə qalarkən, $(i, j)$ hüceyrəsi aşağıdakı sütunlara keçə bilər

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

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

Hərəkət qrafiki qeyri-istikamətlidir (əgər $(i, j)$ -dən $(x, y)$ -ə keçə bilsək, o zaman $(x, y)$ -dən $(i, j)$ -ə də keçə bilərik), biz konsert hüceyrəsindən $(n_{1}, m_{1})$ (n_1,m_1) başlayaraq BFS icra edirik. $ans [i] [j]$ \text{ans}[i][j] $(i, j)$ -dən konsertə çatmaq üçün tələb olunan minimum hərəkət sayını göstərir. Hər bir sətir $i$ üçün, o sətirdəki bütün ziyarət edilməmiş sütunları saxlayan bir dəst saxlayırıq.

BFS vəziyyətini $(x, y)$ emal edərkən, əvvəlcə $x$ sətirini emal edirik. $[l [x] [y], r [x] [y]]$ [l[x][y], r[x][y]] sütunlarındakı hər bir ziyarət edilməmiş hüceyrəyə bir hərəkət ilə çatmaq mümkündür, buna görə onlara məsafə $ans [x] [y] + 1$ \text{ans}[x][y]+1 təyin edirik və BFS növbəsinə əlavə edirik.

Sonra yuxarıya doğru genişlənirik. $i = x + 1, x + 2, \dots$ i = x+1, x+2, \dots sətirləri üçün, $(i, y)$ hüceyrəsi düz olduğu müddətcə və ya ziyarət edilməmişdirsə, ya da məsafəsi $ans [x] [y]$ \text{ans}[x][y]-dən daha böyükdürsə, biz kəsişməni saxlayırıq

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

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

Bu intervallarda olan $i$ sətirindəki ziyarət edilməmiş hüceyrələr bir hərəkət ilə çatmaq mümkündür və məsafə $ans [x] [y] + 1$ \text{ans}[x][y]+1 ilə BFS növbəsinə əlavə edilir. Eyni proses aşağıya doğru $i = x - 1, x - 2, \dots$ i = x-1, x-2, \dots sətirləri üçün simmetrik olaraq tətbiq edilir.

Bir hüceyrə ziyarət edildikdə, o, öz sətir dəstindən çıxarılır və bir daha emal edilməyəcək.

Niyə şaquli genişlənməni dayandırmağın düzgün olduğunu görmək üçün, bir sütun $y$ götürün və düz hüceyrələrin birləşmiş şaquli seqmentini nəzərdən keçirin. Belə bir seqmentin içində məsafələr yalnız iki ardıcıl dəyəri, $d$ və ya $d + 1$ d+1 ala bilər, çünki əgər bir hüceyrə $d$ hərəkət ilə çatmaq mümkündürsə, eyni seqmentdəki hər hansı digər hüceyrəyə ən çox bir əlavə hərəkət ilə çatmaq mümkündür. Buna görə də, məsafəsi $ans [x] [y]$ \text{ans}[x][y]-dən kiçik olmayan bir sətirə çatdıqda, o istiqamətdə daha irəliləmək yeni bir hüceyrənin daha yaxşı məsafə ilə yaranmasına səbəb ola bilməz, çünki bu hüceyrələrə artıq daha yaxşı və ya bərabər vəziyyətdən çatmaq optimal olardı.

Bu, həmçinin səmərəliliyi təmin edir. Məsafəsi $d + 1$ d+1 olan hüceyrələr heç vaxt şaquli genişlənmir, və məsafəsi $d$ olan hüceyrələr yalnız məsafəsi $d$ olan digər hüceyrə ilə qarşılaşana qədər genişlənir. Beləliklə, şaquli seqmentdəki hər bir hüceyrə ən çox iki dəfə şaquli genişlənmədə iştirak edir. Dəst əməliyyatlarının logaritmik xərci ilə birləşdirildikdə.

Ümumi mürəkkəblik $O (n \cdot m \cdot lo g m)$ O(n \cdot m \cdot \log m)-dir.

Tətbiq

#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 << "BƏLİ" << "\n";
#define no cout << "XAHİŞ ETMİRƏM" << "\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
        }
    }
}