qq_52036005 2021-10-28 21:15 采纳率: 100%
浏览 32
已结题

数构结构算法题,有无详细题思路

一匹马在8*8的棋盘上的A处,他的家在B处。他受伤了,每次只有4种走法。如果现在在(x,y)处,能走到的点是:(x+2,y+1),(x-1,y-2),(x+1,y-2),(x-2,y+1)。请你编程求出他回到B处的最小步数。输入有若干种情况。每种情况一行,每行有4个数ax,ay,bx,by,表示点A和点B的坐标。对应输出马走的最小步数。
Sample Input
1 1 2 3
8 8 6 6
Sample Output
Case 1:5
Case 2:4

  • 写回答

2条回答 默认 最新

  • 关注

    用广度优先遍历求最短路径

    你题目的解答代码如下:

    #include <stdio.h>
    int pgo(int ax,int ay,int bx,int by)
    {
        int da[][2] = {{2,1},{-1,-2},{1,-2},{-2,1}};
        int a[64][2];
        int b[64][2];
        int (*p)[2] = a;
        int (*q)[2] = b;
        int l=1,k,n=0,x,y,tx,ty;
        p[0][0] = ax;
        p[0][1] = ay;
        while (l>0)
        {
            k = 0;
            int ta[64] = {0};
            for (int i = 0; i < l; i++)
            {
                x = p[i][0];
                y = p[i][1];
                if (x==bx && y==by)
                    return n;
                for (int j = 0; j < 4; j++)
                {
                    tx = x+da[j][0];
                    ty = y+da[j][1];
                    if (tx>=1 && tx<=8 && ty>=1 && ty<=8 && ta[(ty-1)*8+(tx-1)] != 1)
                    {
                        q[k][0] = tx;
                        q[k][1] = ty;
                        k++;
                        ta[(ty-1)*8+(tx-1)] = 1;
                    }
                }
            }
            int (*r)[2] = p;
            p = q;
            q = r;
            l = k;
            n++;
        }
        return -1;
    }
    int main()
    {
        int i = 1;
        int ax,ay,bx,by;
        while (scanf("%d%d%d%d",&ax,&ay,&bx,&by)!=EOF)
        {
            printf("Case %d:%d\n",i,pgo(ax,ay,bx,by));
            i++;
        }
        return 0;
    }
    

    img

    如有帮助,望采纳!谢谢!

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 3月7日
  • 已采纳回答 2月27日
  • 创建了问题 10月28日

悬赏问题

  • ¥20 matlab中的双层数值积分
  • ¥50 服务器打印水晶报表问题
  • ¥15 Delphi image图片缩放问题
  • ¥30 gradle环境下javafx项目如何使用druid连接池
  • ¥15 服务器打印水晶报表问题
  • ¥15 初学者用plt报错,求解答
  • ¥18 深度学习tensorflow1,ssdv1,coco数据集训练一个模型
  • ¥100 关于注册表摄像头和麦克风的问题
  • ¥30 代码本地运行正常,但是TOMCAT部署时闪退
  • ¥15 关于#python#的问题