Go to diff to previous submission
#include<iostream> #include<vector> #include<algorithm> #include<map> #include<set> #include<list> #include<stack> #include<queue> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> using namespace std; #define FOR(i,a,b) for(int i=a;i<=b;i++) #define PB push_back #define PII pair<int,int> #define PLL pair<ll,ll> #define MP make_pair #define fi first #define se second #define SIZE(s) (int) (s).size() #define INF 987654321 #define ll long long //---------------------- #define MAX 147 int X,Y; int beginY, beginX; int endX, endY; int D[MAX][MAX]; int diry[8] = {1,2,2,1,-1,-2,-2,-1}; int dirx[8] = {2,1,-1,-2,-2,-1,1,2}; bool ok(int y, int x) { return (y >= 0 && y < Y) && (x >= 0 && x < X); } int bfs() { FOR(i,0,Y-1) FOR(j,0,X-1) D[i][j] = 0; queue< PII > Q; Q.push(MP(beginY,beginX)); while(!Q.empty()) { PII front = Q.front(); Q.pop(); int d = D[front.fi][front.se]; if (front.fi == endY && front.se == endX) return d; FOR(dir,0,7) { int y = front.fi + diry[dir]; int x = front.se + dirx[dir]; if (ok(y,x) && D[y][x] == 0) { D[y][x] = d+1; Q.push(MP(y,x)); } } } return -1; } int main() { while(scanf("%d %d %d %d %d %d",&Y,&X,&beginY,&beginX,&endY,&endX) == 6) { beginX--; beginY--; endX--; endY--; int res = bfs(); if (res==-1) printf("impossible\n"); else printf("%d\n",res); } return 0; }