grasshop.cpp

#include <cstdio>
#include <iostream>
#include <queue>
 
using namespace std;
 
int R; // Row count 
int C; // column count
int Gr; // row pos grasshopper
int Gc; // column pos grasshopper
int Lr; // row pos delicious
int Lc; // column pos delicious
 
class Position
{
  public:
    int first;
    int second;
    int hops;
 
    Position(int a, int b, int hops = 0)
    {
        first = a;
        second = b;
        this->hops = hops;
    }
 
    bool operator==(const Position &pos)
    {
        if (this->first == pos.first && this->second == pos.second)
          return true;
 
        return false;
    }  
};
 
queue<Position> q;
 
#define boardSize 100
bool board[boardSize][boardSize];
 
 
void clearBoard(int xsize, int ysize)
{
    for (int i = 0 ; i < xsize ; ++i)
        for (int j = 0 ; j < ysize ; ++j)
          board[i][j] = false;
}
 
bool validPos(Position pos)
{
 
 
    if (pos.first < 0 || pos.first >= R)
      return false;
 
    if (pos.second < 0 || pos.second >= C)
      return false;
 
    if (board[pos.first][pos.second])
      return false;
 
    return true;
}
 
 
void generateHops(Position actual)
{
   Position p1 = Position(actual.first-1, actual.second+2, actual.hops+1);
   Position p2 = Position(actual.first+1, actual.second+2, actual.hops+1);
   Position p3 = Position(actual.first+2, actual.second+1, actual.hops+1);
   Position p4 = Position(actual.first+2, actual.second-1, actual.hops+1);
   Position p5 = Position(actual.first+1, actual.second-2, actual.hops+1);
   Position p6 = Position(actual.first-1, actual.second-2, actual.hops+1);
   Position p7 = Position(actual.first-2, actual.second-1, actual.hops+1);
   Position p8 = Position(actual.first-2, actual.second+1, actual.hops+1);
 
   if (validPos(p1))
    q.push(p1);
   if (validPos(p2))
    q.push(p2);
   if (validPos(p3))
    q.push(p3);
   if (validPos(p4))
    q.push(p4);
   if (validPos(p5))
    q.push(p5);
   if (validPos(p6))
    q.push(p6);
   if (validPos(p7))
    q.push(p7);
   if (validPos(p8))
    q.push(p8);
}
 
int main()
{
 
  while (true)
  {
 
    cin >> R;
    if (cin.eof())
      break;
    cin >> C;
    cin >> Gr;
    cin >> Gc;
    cin >> Lr;
    cin >> Lc;
 
    Gr--;Gc--;
    Lr--;Lc--;
 
    Position target = Position(Lr, Lc);
    clearBoard(R,C);
    while (!q.empty())
      q.pop();
 
    q.push(Position(Gr,Gc));
    while (!q.empty())
    {
      Position actual = q.front();
      board[actual.first][actual.second] = true;
      q.pop();
      if (actual == target)
      {
        cout << actual.hops << endl;
        q.push(target);
        break;
      }
 
      generateHops(actual);
 
    }
    if (q.empty())
      cout << "impossible" << endl;
  }
 
 
  return 0;
}