Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <ctype.h> #include <math.h> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> #include <queue> using namespace std; typedef pair <int, int> PII; typedef long long int LL; typedef vector <int> VI; typedef vector <LL> VLL; #define FOR(i, a, b) for ( int i = a; i < b; ++i ) #define FORD(i, a, b) for ( int i = a-1; i >= 0; --i ) #define FILL(x, v, n) for ( int _i = 0; _i < n; ++_i ) x[_i] = v; int dx[ 8 ] = { 2, 2, -2, -2, 1, 1, -1, -1 }; int dy[ 8 ] = { 1, -1, 1, -1, 2, -2, 2, -2 }; bool vis[ 101 ][ 101 ]; struct State { int x, y, d; }; int main() { int R, C, gr, gc, lr, lc; while ( scanf( "%d %d %d %d %d %d", &R, &C, &gr, &gc, &lr, &lc ) == 6 ) { --gr; --gc; --lr; --lc; FOR(i,0,R)FOR(j,0,C) vis[ i ][ j ] = false; int res = -1; queue< State > q; State st; st.x = gc; st.y = gr; st.d = 0; q.push( st ); while ( !q.empty() ) { State s = q.front(); q.pop(); if ( s.x == lc && s.y == lr ) { res = s.d; break; } State ns; FOR(i,0,8) { ns.x = s.x + dx[i]; ns.y = s.y + dy[i]; ns.d = s.d + 1; if ( ns.x < 0 || ns.y < 0 || ns.x >= C || ns.y >= R || vis[ ns.y ][ ns.x ] ) continue; vis[ ns.y ][ ns.x ] = true; q.push( ns ); } } if ( res == -1 ) printf( "impossible\n" ); else printf( "%d\n", res ); } return 0; }