Click here to Skip to main content
15,902,198 members
Please Sign up or sign in to vote.
1.50/5 (2 votes)
See more:
[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;
    }
}
Posted
Updated 9-Aug-17 10:47am
Comments
Patrice T 7-Aug-17 17:17pm    
Do you have a question related to this code ?

1 solution

Google gave me this:Chess Knight Problem | Find Shortest path from source to destination[^]

It's pretty close to what you need, as you know where the pawn is going to be in x number of steps ...

Best regards
Espen Harlinn
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900