grasshop.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
 
using namespace std;
 
typedef unsigned long int ulint;
 
ulint R, C, GR, GC, LR, LC;
 
static ulint visited[150][150];
 
struct point
{
    point () {}
    point (ulint x, ulint y) : x(x), y(y) {}
    ulint x;
    ulint y;
};
 
static int drow[] = {1,1,2,2,-1,-1,-2,-2};
static int dcol[] = {2,-2,1,-1,2,-2,1,-1};
 
inline void solve()
{
    visited[GR][GC] = 1;
 
    queue<point> bfsq;
    bfsq.push(point(GR, GC));
 
    point curr;
    while (!bfsq.empty())
    {
        curr = bfsq.front();
        bfsq.pop();
 
        ulint nx;
        ulint ny;
        for (uint d = 0; d < 8; ++d)
        {
            nx = curr.x + drow[d];
            ny = curr.y + dcol[d];
 
            if (nx > 0 && nx < R && ny > 0 && ny < C && visited[nx][ny] == 0)
            {
                visited[nx][ny] = visited[curr.x][curr.y] + 1;
                bfsq.push(point(nx, ny));                
            }
        }
    }
 
    if (visited[LR][LC] > 0)
    {
        printf("%lu\n", visited[LR][LC] - 1);
    }
    else
    {
        printf("impossible\n");
    }
}
 
int main()
{
    while (scanf("%lu %lu %lu %lu %lu %lu", &R, &C, &GR, &GC, &LR, &LC) != EOF)
    {
        memset(visited, 0, sizeof(visited));
        solve();
    }
}