Tranvick

Untitled

Mar 6th, 2012
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:65777216")
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <set>
  11. #include <stack>
  12. #include <map>
  13. #include <queue>
  14. #include <string>
  15. #include <memory.h>
  16. #include <iterator>
  17. #define y1 trololoy1
  18. #define y0 trololoy0
  19. #define mem(A,X) memset(A,X,sizeof(A))
  20. #define memo(A) memset(A,0,sizeof(A))
  21. #define forn(I,B) for (int I=1;I<=(B);I++)
  22. #define forg(H,V) for (int H=first[V];h;h=next[H])
  23. #define rep(I,B) for (int I=0;I<(B);I++)
  24. #define labs(X) (((X)>0)?(X):(-(X)))
  25. #define ropen(X) freopen(X,"r",stdin)
  26. #define wopen(X) freopen(X,"w",stdout)
  27. #define rwopen(X) freopen(X".in","r",stdin);freopen(X".out","w",stdout)
  28. #define pb push_back
  29. #define mp make_pair
  30. #define all(X) (X).begin(),(X).end()
  31. #define sqr(X) ((X)*(X))
  32.  
  33. using namespace std;
  34.  
  35. typedef pair <int,int> pii;
  36. typedef double ld;
  37. typedef long long ll;
  38. typedef pair <ll,ll> pll;
  39. typedef vector<int> vi;
  40. const int N=1111;
  41. const int INF=111111111;
  42. const double eps=1e-9;
  43. const double pi=3.14159265358979;
  44.  
  45. deque<int> qx,qy;
  46. int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
  47. int d[N][N],xs,ys,n,a[N][N];
  48.  
  49. void bfs(){
  50.     int n=1001,m=1001;
  51.     qx.push_front(xs);
  52.     qy.push_front(ys);
  53.     mem(d,63);d[xs][ys]=0;
  54.     while (!qx.empty()){
  55.         int x=qx.front(),y=qy.front();
  56.         qx.pop_front();qy.pop_front();
  57.         rep(i,4){
  58.             if (x+dx[i]>n || x+dx[i]<0 || y+dy[i]>n || y+dy[i]<0) continue;
  59.             if (a[x+dx[i]][y+dy[i]] && d[x+dx[i]][y+dy[i]]>d[x][y]+1){
  60.                 d[x+dx[i]][y+dy[i]]=d[x][y]+1;
  61.                 qx.push_back(x+dx[i]);
  62.                 qy.push_back(y+dy[i]);
  63.             }
  64.             if (!a[x+dx[i]][y+dy[i]] && d[x+dx[i]][y+dy[i]]>d[x][y]){
  65.                 d[x+dx[i]][y+dy[i]]=d[x][y];
  66.                 qx.push_front(x+dx[i]);
  67.                 qy.push_front(y+dy[i]);
  68.             }
  69.         }
  70.     }
  71. }
  72.  
  73. int main(){
  74.     rwopen("tractor");
  75.     scanf("%d%d%d",&n,&xs,&ys);
  76.     forn(i,n){
  77.         int A,B;
  78.         scanf("%d%d",&A,&B);
  79.         a[A][B]=1;
  80.     }
  81.     bfs();
  82.     printf("%d\n",d[0][0]);
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment