Pagini recente » Cod sursa (job #3305227) | Cod sursa (job #3033107) | Cod sursa (job #1266709) | Cod sursa (job #492581) | Cod sursa (job #3347364)
#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;
}