knight.cpp

#include <iostream>
#include <string>
#include <queue>
//#include <tuple>
 
#define uint unsigned int
 
int dx[] = {-1,1,2,2,1,-1,-2,-2};
int dy[] = {-2,-2,-1,1,2,2,1,-1};
 
using namespace std;
 
int main()
{
    uint r,c,gr,gc,lr,lc;
 
    while(cin >> r >> c >> gr >> gc >> lr >>lc)
    {
        gr--; gc--; lr--; lc--;
 
        if(gr == lr && gc == lc)
        {
            cout << "0" << endl;
            continue;
        }
 
        unsigned int field[r][c];
        for(uint i = 0; i < r; i++)
        for(uint j = 0; j < c; j++)
        {
            field[i][j] = 1000;
        }
 
        field[gr][gc] = 0;
 
        queue<pair<uint,uint> > fronta;
        fronta.push(pair<uint,uint>(gr,gc));
 
        bool found = false;
 
        while(!fronta.empty() && !found)
        {
            pair<uint,uint> p = fronta.front();
            fronta.pop();
 
            for(int i = 0; i < 8; i++)
            {
                int row = p.first + dy[i];
                int col = p.second + dx[i];
                if(row < 0 || col < 0 || row >= r || col >= c) continue;
 
                if(field[row][col] == 1000)
                {
                    uint dist = field[p.first][p.second] + 1;
                    field[row][col] = dist;
                    if(row == lr && col == lc)
                    {
                        found = true;
                        cout << dist;
                    }
                    fronta.push(pair<uint,uint>(row,col));
                }
            }
        }
 
        if(!found)
            cout << "impossible";
        cout << endl;
    }
 
    return 0;
 
}