Cod sursa(job #3347364)

Utilizator iustin.dumiDumitrescu Iustin iustin.dumi Data 16 martie 2026 14:43:57
Problema Dusman Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("labir.in");
ofstream fout("labir.out");
int n,m,i,j,k,xs,ys,xf,yf,vl[5005],vc[5005],s,l,c,t;
int di[4]={0,0,1,-1},dj[4]={1,-1,0,0};
int a[2505][2505];
bitset<2505> b[2505];
queue<pair<int,int>> q;
bool ok(int i, int j)
{
    return i&&j&&i<=n&&j<=m;
}
int main()
{
    fin>>n>>m;
    fin>>xs>>ys>>xf>>yf;
    fin>>k;
    for(i=1;i<=k;i++)
    {
        fin>>l>>c;
        q.push(make_pair(l,c));
        vl[l]=1;
        vc[c]=1;
    }
    vl[xs]=vc[ys]=vl[xf]=vc[yf]=1;
    l=0;
    s=0;
    for(i=1;i<=n;i++)
    {
        if(!vl[i]) l++;
        else
        {
            if(l>1) s+=l-1;
            l=0;
            vl[i]=i-s;
        }
    }
    if(l>1) s+=l-1;
    n-=s;
    l=0;
    s=0;
    for(i=1;i<=m;i++)
    {
        if(!vc[i]) l++;
        else
        {
            if(l>1) s+=l-1;
            l=0;
            vc[i]=i-s;
        }
    }
    if(l>1) s+=l-1;
    m-=s;
    for(i=1;i<=k;i++)
    {
        l=q.front().first;
        c=q.front().second;
        b[vl[l]][vc[c]]=1;
        q.pop();
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) a[i][j]=2000000000;
    q.push(make_pair(vl[xs],vc[ys]));
    a[vl[xs]][vc[ys]]=0;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(t=0;t<4;t++)
        {
            int iv=i+di[t];
            int jv=j+dj[t];
            if(ok(iv,jv) && a[i][j]+b[iv][jv]<a[iv][jv])
            {
             a[iv][jv]=a[i][j]+b[iv][jv];
             q.push(make_pair(iv,jv));
            }
        }
    }
    fout<<a[vl[xf]][vc[yf]];
    return 0;
}