Концерт Міку#12334

Концерт Міку (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Для кожної рівної клітинки $(i, j)$ ми попередньо обчислюємо горизонтальний інтервал у її рядку, який можна досягти без перетворення пагорба. Нехай $l [i] [j]$ l[i][j] буде найлівішою колонкою, доступною з $(i, j)$ у рядку $i$ , а $r [i] [j]$ r[i][j] буде найправішою. Ці значення обчислюються шляхом сканування кожного рядка зліва направо та справа наліво. Таким чином, залишаючись у тому ж рядку, клітинка $(i, j)$ може переміститися в будь-яку колонку в

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

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

Оскільки граф переміщення є ненаправленим (якщо ми можемо переміститися з $(i, j)$ до $(x, y)$ , то ми також можемо переміститися з $(x, y)$ до $(i, j)$ ), ми запускаємо BFS, починаючи з клітинки концерту $(n_{1}, m_{1})$ (n_1,m_1). Нехай $ans [i] [j]$ \text{ans}[i][j] позначає мінімальну кількість переміщень, необхідних для досягнення концерту з $(i, j)$ . Для кожного рядка $i$ ми підтримуємо множину, що містить усі неперевірені колонки в цьому рядку.

Обробляючи стан BFS $(x, y)$ , спочатку обробляємо рядок $x$ сам по собі. Кожна неперевірена клітинка в колонках $[l [x] [y], r [x] [y]]$ [l[x][y], r[x][y]] може бути досягнута за один хід, тому ми присвоюємо їм відстань $ans [x] [y] + 1$ \text{ans}[x][y]+1 і додаємо їх у чергу BFS.

Потім ми розширюємо вгору. Для рядків $i = x + 1, x + 2, \dots$ i = x+1, x+2, \dots, поки клітинка $(i, y)$ є рівною і або неперевіреною, або має строго більшу відстань, ніж $ans [x] [y]$ \text{ans}[x][y], ми підтримуємо перетин

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

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

Усі неперевірені клітинки в рядку $i$ , стовпці яких лежать у цьому інтервалі, досяжні за один хід і додаються до черги BFS з відстанню $ans [x] [y] + 1$ \text{ans}[x][y]+1. Такий же процес застосовується симетрично вниз для рядків $i = x - 1, x - 2, \dots$ i = x-1, x-2, \dots.

Якщо клітинка була перевірена, вона видаляється з набору рядка і більше ніколи не буде оброблена.

Щоб зрозуміти, чому правильно зупинити вертикальне розширення, як тільки ми зустрічаємо клітинку $(i, y)$ з

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

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

зафіксуємо стовпець $y$ і розглянемо один зв'язаний вертикальний сегмент рівних клітин. У межах такого сегмента відстані можуть приймати лише два послідовні значення, $d$ або $d + 1$ d+1, оскільки якщо одна клітинка досяжна за $d$ ходів, будь-яка інша клітинка в тому ж сегменті може бути досягнута максимум за один додатковий хід. Тому, як тільки ми досягаємо рядка з відстанню, що не перевищує $ans [x] [y]$ \text{ans}[x][y], подальше просування в цьому напрямку не може дати нову клітинку з кращою відстанню, оскільки завжди буде оптимально досягти цієї клітинки з уже кращого або рівного стану.

Це також гарантує ефективність. Клітинки з відстанню $d + 1$ d+1 ніколи не розширюються вертикально, а клітинки з відстанню $d$ розширюються лише до тих пір, поки не зустрінуть іншу клітинку з відстанню $d$ . Отже, кожна клітинка в вертикальному сегменті бере участь у вертикальному розширенні максимум двічі. У поєднанні з логарифмічною вартістю операцій з множинами.

Загальна складність становить $O (n \cdot m \cdot lo g m)$ O(n \cdot m \cdot \log m)

Реалізація

#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
        }
    }
}