grasshop.cpp
#include <iostream>
#include <cstdlib>
#include <vector>
#include <list>
#include <map>
using namespace std;
int gR, gC, r, c, lR, lC;
struct State {
int r, c;
int steps;
};
int arrR[]= {-2, -1, 1, 2, 2, 1, -1, -2};
int arrC[] = {1, 2, 2, 1, -1, -2, -2, -1};
int solve ( bool ** chessBoard){
list <State> l;
State s;
s.r = gR;
s.c = gC;
s.steps = 0;
l.push_back(s);
while (!l.empty()){
State t = *(l.begin());
l.pop_front();
for (int i = 0; i < 8 ; i++){
int tR = t.r + arrR[i];
int tC = t.c + arrC[i];
if (tR <= 0 || tR > r || tC <= 0 || tC > c){
continue;
}
if (chessBoard[tR][tC]) continue;
chessBoard[tR][tC] = true;
State tmp;
tmp.r = tR;
tmp.c = tC;
tmp.steps = t.steps + 1;
l.push_back(tmp);
if (tmp.r == lR && tmp.c == lC){
return tmp.steps;
}
}
}
return -1;
}
int main(){
bool ** chessBoard;
while ( cin >> r >> c >> gR >> gC >> lR >> lC){
if (gR == lR && gC == lC) {
cout << 0 << endl;
continue;
}
chessBoard = new bool * [r];
for (int i = 0; i <= r ; i++){
chessBoard[i] = new bool[c];
for (int j = 0; j <= c; j++){
chessBoard[i][j] = false;
}
}
chessBoard[gR][gC] = true;
int result = solve(chessBoard);
if (result < 0){
cout << "impossilble" << endl;
} else {
cout << result << endl;
}
for (int i = 0; i <= r ; i++){
delete [] chessBoard[i];
}
// delete [] chessBoard;
}
return 0;
}