BFS的骑士和典当最短的问题 [英] Knight and pawn's shortest question by BFS

问题描述

[HELP]

国际象棋有无限大小，骑士在Mx，我可以移动8个方向（作为国际象棋的规则）而Pawn是在Tx，Ty但是只是上升（Tx，Ty-> Tx + 1，Ty）。

问题：如果骑士先行动，我们需要多少步才能让骑士吃掉Pawn？

链接问题：http：//vn.spoj.com/问题/ KANDP /

我只是想知道如何使用BFS找到他们移动时从骑士到Pawn的最短路:(抱歉我的英语，我是VietNamese女孩......刚开始。请帮助



我尝试过：

[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;
    }
}

推荐答案

谷歌给了我这个：骑士问题找到从源到目的地的最短路径 [ ^ ]



它非常接近你所需要的，因为你知道pawn将在x的位置步骤...



最好的问候

Espen Harlinn

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

这篇关于BFS的骑士和典当最短的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！