马的移动（BFS）

骑猪看日落 2022-06-07 13:37 113阅读 0赞

//题意自己看，不会度娘

#include <stdio.h>
    #include <queue>
    #include <string.h>
    struct node
    {
    	int x;
    	int y;
    	int step;
    };
    int map[8][8];//标记数组 
    int sx,sy,ex,ey,ans;
    int move[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};//方向数组控制方向 
    
    int cheak(int x,int y)//检查是否符合要求 
    {
    	if(x<0||y<0||x>=8||y>=8)//是否越界 
    		return 1;
    	if(map[x][y])//已经使用过 
    		return 1;
    	return 0;	
    }
    void BFS()
    {
    	queue<node>we;//建立队列 
    	node a,next;//建立结构体 
    	a.x=sx;
    	a.y=sy;//起点坐标赋值 
    	a.step=0;//步数为0 
    	map[sx][sy]=1;//标记为1代表已经走过 
    	we.push(a);//放入 
    	while(!we.empty())
    	{
    		a=we.front();
    		we.pop();
    		if(a.x==ex&&a.y==ey)
    		{
    			ans=a.step;
    			return ;
    		}//找到终点 
    		for(int i=0;i<8;i++)//8方向循环 
    		{
    			next=a;
    			next.x+=move[i][0];
    			next.y+=move[i][1];
    			if(cheak(next.x,next.y))
    				continue;
    			next.step=a.step+1;
    			map[next.x][next.y]=1;
    			we.push(next);
    				
    		}		
    	}
    	return ;
    }
    
    int main(int argc, char *argv[])
    {
    	char c1[10],c2[20];
    	while(scanf("%s %s",c1,c2)!=EOF)
    	{
    		sx=c1[0]-'a';//坐标转化为字符型 
    		sy=c1[1]-'1';//坐标转化为数字 
    		ex=c2[0]-'a';//同上 
    		ey=c2[1]-'1';
    		memset(map,0,sizeof(map));
    		BFS();
    		printf("To get from %s to %s takes %d knight moves.\n",c1,c2,ans);
    	}	
    	return 0;
    }

//Start-ZJ

//2017/10/23/11:25

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关 BFS

一、什么是BFS 广度优先算法（Breadth-First-Search），简称BFS，是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发

比眉伴天荒/ 2024年02月18日 20:09/ 0 赞/ 16 阅读

相关 BFS

BFS 的使用条件: 简单图(没有权重)可以找最短路径 BFS 模板: 建一个Queue，先将起点放入Queue中,然后根据题目要求得到下一层的点(可达方向

爱被打了一巴掌/ 2022年10月01日 11:55/ 0 赞/ 125 阅读

相关 BFS的应用

BFS在二叉树上的应用二叉树的层次遍历 // 一颗二叉树 1 / \ 2

谁借莪１个温暖的怀抱￠/ 2022年09月25日 15:23/ 0 赞/ 86 阅读

相关 P1443 马的遍历（bfs）

注意左对齐，宽五格的输出，为此wa了两次 include <bits/stdc++.h> using namespace std; define in

短命女/ 2022年08月30日 15:58/ 0 赞/ 118 阅读

相关 bfs 马的移动

小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？现请你编程解决这个问题。

青旅半醒/ 2022年08月03日 16:52/ 0 赞/ 125 阅读

相关 BFS

总体感悟广搜的话，占内存多，能找到最优解，必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法。BFS在求解最短路径或者最短步数上有很多的应用。应用最多的是在

谁借莪１个温暖的怀抱￠/ 2022年08月03日 16:51/ 0 赞/ 154 阅读

相关马的移动（BFS）

//题意自己看，不会度娘 include <stdio.h> include <queue> include <string.h> s

骑猪看日落/ 2022年06月07日 13:37/ 0 赞/ 114 阅读

相关 HRBUST 1181 移动 bfs模板

1 include<bits/stdc++.h>///该头文件为万能头文件，有些学校oj不能使用，读者可根据需要自行修改 2 using namespace

分手后的思念是犯贱/ 2022年01月06日 11:45/ 0 赞/ 137 阅读

相关 174. 推箱子（bfs+bfs）

题目链接：[https://www.acwing.com/problem/content/description/176/][https_www.acwing.com_prob

比眉伴天荒/ 2021年11月10日 15:50/ 0 赞/ 370 阅读

相关洛谷P1443 马的遍历(bfs)

[https://www.luogu.org/problem/P1443][https_www.luogu.org_problem_P1443] 思路：马走日字格，它可以走十

谁借莪１个温暖的怀抱￠/ 2021年10月18日 15:44/ 0 赞/ 325 阅读