bfs 马的移动

青旅半醒 2022-08-03 16:52 170阅读 0赞

小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：

给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？

现请你编程解决这个问题。

简单的bfs问题，和上一篇一样可以作为bfs的简单模板

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    int sx,sy; //起始坐标
    int ex,ey; //目标坐标
    char s[5],e[5];
    int map[9][9];  //地图
    int dir[8][2]={
       {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}}; //二维空间马走日移动
    struct node
    {
    	int x,y,step;
    };
    
    void bfs()
    {
    	queue<node>q;  //建立node型的一个队列
    	node cur,next;
    	cur.x=sx;
    	cur.y=sy;
    	cur.step=0;
    	map[sx][sy]=1;  //已遍历则将该位置记为,不再处理该位置
            //root 根节点
    	q.push(cur);         //将cur置入队列
    	while(!q.empty())    //判断队列是否为空，不为空则进入
    	{
    		cur=q.front();  //返回第一个置入的元素,cur赋值为第一个置入的元素
    		q.pop();         //移除该返回的元素
    		for(int i=0;i<8;i++)   //遍历cur的下一层
    		{
    			next.x=cur.x+dir[i][0];
    			next.y=cur.y+dir[i][1];
    			next.step=cur.step + 1;
    			if(next.x>=0&&next.y>=1&&next.x<8&&next.y<=8
    				&&map[next.x][next.y]==0)
    			{
    				if(next.x==ex&&next.y==ey)
    				{
    					printf("To get from %s to %s takes %d knight moves.\n", s,e,next.step);
    					return ;
    				}
    				map[next.x][next.y]=1;
    				q.push(next);     //将next置入队列中
    			}
    		}
    	}
    }
    int main()
    {
    	while(scanf("%s %s",s,e)!=EOF)
    	{
    	    sx=s[0]-'a';sy=s[1]-'0';          //x为0到7，y为1到8
    	    ex=e[0]-'a';ey=e[1]-'0';
    	    memset(map,0,sizeof(map));
    		if(sx==ex&&sy==ey)
    		{
    		    printf("To get from %s to %s takes %d knight moves.\n", s,e,0);
    			continue;
    		}
    		bfs();
    	}
    	return 0;
    }