grasshop.cpp
#include <iostream>
#include <list>
using namespace std;
int R, C;
int grid[100][100];
list<int> fifo;
bool hop(int r, int c, int dr, int dc) {
if ((r+dr)>=0 && (r+dr)<R && (c+dc)>=0 && (c+dc)<C) {
if (grid[r+dr][c+dc] == -1)
return true;
else if (grid[r+dr][c+dc] == 0) {
grid[r+dr][c+dc]=grid[r][c]+1;
fifo.push_back(r+dr);
fifo.push_back(c+dc);
}
}
return false;
}
int main(int argc, char** argv){
int GR, GC, LR, LC, r, c;
while (cin >> R >> C) {
fifo.clear();
for (r=0; r<R;r++)
for (c=0; c<C; c++)
grid[r][c]=0;
cin >> GR >> GC >> LR >> LC;
grid[GR][GC]=1;
grid[LR][LC]=-1;
fifo.push_back(GR);
fifo.push_back(GC);
while (!fifo.empty()) {
r = fifo.front(); fifo.pop_front();
c = fifo.front(); fifo.pop_front();
if (hop(r,c,1,2) || hop(r,c,2,1) || hop(r,c,2,-1) || hop(r,c,1,-2) ||
hop(r,c,-1,-2) || hop(r,c,-2,-1) || hop(r,c,-2,1) || hop(r,c,-1,2)) {
cout << grid[r][c] << endl;
break;
}
}
if (fifo.empty()) cout << "impossible" << endl;
}
return 0;
}