Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:65777216")
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <stack>
- #include <map>
- #include <queue>
- #include <string>
- #include <memory.h>
- #include <iterator>
- #define y1 trololoy1
- #define y0 trololoy0
- #define mem(A,X) memset(A,X,sizeof(A))
- #define memo(A) memset(A,0,sizeof(A))
- #define forn(I,B) for (int I=1;I<=(B);I++)
- #define forg(H,V) for (int H=first[V];h;h=next[H])
- #define rep(I,B) for (int I=0;I<(B);I++)
- #define labs(X) (((X)>0)?(X):(-(X)))
- #define ropen(X) freopen(X,"r",stdin)
- #define wopen(X) freopen(X,"w",stdout)
- #define rwopen(X) freopen(X".in","r",stdin);freopen(X".out","w",stdout)
- #define pb push_back
- #define mp make_pair
- #define all(X) (X).begin(),(X).end()
- #define sqr(X) ((X)*(X))
- using namespace std;
- typedef pair <int,int> pii;
- typedef double ld;
- typedef long long ll;
- typedef pair <ll,ll> pll;
- typedef vector<int> vi;
- const int N=1111;
- const int INF=111111111;
- const double eps=1e-9;
- const double pi=3.14159265358979;
- deque<int> qx,qy;
- int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
- int d[N][N],xs,ys,n,a[N][N];
- void bfs(){
- int n=1001,m=1001;
- qx.push_front(xs);
- qy.push_front(ys);
- mem(d,63);d[xs][ys]=0;
- while (!qx.empty()){
- int x=qx.front(),y=qy.front();
- qx.pop_front();qy.pop_front();
- rep(i,4){
- if (x+dx[i]>n || x+dx[i]<0 || y+dy[i]>n || y+dy[i]<0) continue;
- if (a[x+dx[i]][y+dy[i]] && d[x+dx[i]][y+dy[i]]>d[x][y]+1){
- d[x+dx[i]][y+dy[i]]=d[x][y]+1;
- qx.push_back(x+dx[i]);
- qy.push_back(y+dy[i]);
- }
- if (!a[x+dx[i]][y+dy[i]] && d[x+dx[i]][y+dy[i]]>d[x][y]){
- d[x+dx[i]][y+dy[i]]=d[x][y];
- qx.push_front(x+dx[i]);
- qy.push_front(y+dy[i]);
- }
- }
- }
- }
- int main(){
- rwopen("tractor");
- scanf("%d%d%d",&n,&xs,&ys);
- forn(i,n){
- int A,B;
- scanf("%d%d",&A,&B);
- a[A][B]=1;
- }
- bfs();
- printf("%d\n",d[0][0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment