[HELP]
A chess have infinite size, Knight is at Mx, My and can move for 8 directions ( As rules of chess ) and the Pawn is at Tx, Ty but just go up (Tx, Ty -> Tx + 1, Ty) .
The question : If the Knight move first, how many steps do we need to make Knight eat Pawn ?
Link question : http://vn.spoj.com/problems/KANDP/
I just want to know how to use BFS to find shortest way from Knight to Pawn when they are moving :( Sorry about my English, i am VietNamese girl ... just begining .. please help
What I have tried:
int bfs1()
{
int bot1 = 1, top1 = 0;
q1[++top1] = (Node) {mx, my};
cnt = 0;
for ( ; ; ) {
cnt++;
int v = top1;
for (int i = bot1; i <= v; i++) {
Node t = q1[i];
if (t.y == ty ) {
for (int j = 0; j < 4; j++) {
int x = t.x + hx[j];
int y = t.y + hy[j];
if (x > 1000 or y > 1000 or x < 0 or y < 0) continue;
if (d1[x][y] != cnt) {
q1[++top1] = (Node) { t. x + hx[j], t.y + hy[j] };
d1[x][y] = cnt;
}
}
}
else
if (t.y < ty ) {
for (int j = 2; i < 4; j++) {
int x = t.x + hx[j];
int y = t.y + hy[j];
if (x > 1000 or y > 1000 or x < 0 or y < 0) continue;
if (d1[x][y] != cnt) {
q1[++top1] = (Node) { t. x + hx[j], t.y + hy[j] };
d1[x][y] = cnt;
}
}
}
else
for (int j = 0; j < 2; j++) {
int x = t.x + hx[j];
int y = t.y + hy[j];
if (x > 1000 or y > 1000 or x < 0 or y < 0) continue;
if (d1[x][y] != cnt) {
q1[++top1] = (Node) { t. x + hx[j], t.y + hy[j] };
d1[x][y] = cnt;
}
}
}
if (d1[tx][ty] == cnt)
return cnt;
tx = tx + 1;
d2[tx][ty] = cnt;
}
}