SHARE
TWEET

MUD

sonprao Dec 24th, 2018 (edited) 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(i=a;i<=b;i++)
  3. using namespace std;
  4. #define mp(x,y) make_pair(x,y)
  5. int h,k,i,N,a[5010],b[5010],t,u,d[1005][1005],j,x,y;
  6. std::queue < pair<int,int> > q;
  7. bool kt[2005][2005];
  8. int main(){
  9.     cin>>h>>k>>N;
  10.     FOR(i,0,1005)
  11.     FOR(j,0,1005) { kt[i][j]=true; d[i][j]=INT_MAX-1;}
  12.     FOR(i,1,N){ cin>>a[i]>>b[i]; kt[a[i]+501][b[i]+501]=false;}
  13.     d[h+501][k+501]=0;
  14.     q.push(mp(h,k));
  15.     //cout<<endl;
  16.     while (q.size()!=0)
  17.     {
  18.        x=q.front().first;
  19.        y=q.front().second;
  20.        kt[x+501][y+501]=false;
  21.        if ((abs(x)<=500) && (abs(y)<=500))
  22.        {
  23.        if (kt[x+501+1][y+501]==true) { q.push(mp(x+1,y)); kt[x+501+1][y+501]=false;}
  24.        if (kt[x+501-1][y+501]==true) { q.push(mp(x-1,y)); kt[x+501-1][y+501]=false;}
  25.        if (kt[x+501][y+501+1]==true) { q.push(mp(x,y+1)); kt[x+501][y+501+1]=false;}
  26.        if (kt[x+501][y+501-1]==true) { q.push(mp(x,y-1)); kt[x+501][y+501-1]=false;}
  27.        }
  28.        d[x+501][y+501]=min(min(min(min(d[x+1+501][y+501]+1,d[x-1+501][y+501]+1),d[x+501][y+501-1]+1),d[x+501][y+501+1]+1),d[x+501][y+501]);
  29.        if ((x==0)&& (y==0)) break;
  30.        q.pop();
  31.       // cout<<x<<" "<<y<<" "<<d[x+501][y+501]<<endl;
  32.     }
  33.     cout<<d[501][501];
  34.     return 0;
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top