hdu 1372(simple BFS)

水深无声 2021-12-11 11:29 182阅读 0赞

[Problem link adress:click here][Problem link adress_click here]

This is a basic BFS problem.But the way of knight's move  is strange,if you don't know the law of the knight's move,you are likely to cann't work the problem out.However,if you can find the regularity of the problem from the given cases's data,you must be very smart!

#include<iostream>
    #include<queue>
    #include<string>
    using namespace std;
    int map[10][10];
    char s1[5],s2[5];
    int visted[10][10];
    int x1,y1;
    int x2,y2;
    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()
    {
    	int x,y;
    	node cur,next;
    	queue<node>q;
    	memset(visted,0,sizeof(visted));
    	cur.x=x1;
    	cur.y=y1;
    	cur.step=0;
    	visted[x1][y1]=1;
    	q.push(cur);
    	while(!q.empty())
    	{
    		cur=q.front();
    		q.pop();
    		if(cur.x==x2&&cur.y==y2)
    		{
    			printf("To get from %s to %s takes %d knight moves.\n",s1,s2,cur.step);
    			return ;
    		}
    		for(int i=0;i<8;i++)
    		{
    			next.x=x=cur.x+dir[i][0];
    			next.y=y=cur.y+dir[i][1];
    		    next.step=cur.step+1;
    			if(x>=0&&x<8&&y>=0&&y<8)
    			{
    				visted[x][y]=1;
    				q.push(next);
    			}
    
    		}
    	}
    }
    
    
    int main()
    {
    	
    	while(scanf("%s%s",s1,s2)!=EOF)
    	{
    		x1=s1[0]-'a';
    		y1=s1[1]-'1';
    		x2=s2[0]-'a';
    		y2=s2[1]-'1';
    		BFS();
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/heat-man/archive/2012/12/22/2829576.html

[Problem link adress_click here]: http://acm.hdu.edu.cn/showproblem.php?pid=1372

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1254(BFS)

题意：如题。 include <cstdio> include <cstring> include <iostream> include

快来打我*/ 2022年09月20日 12:35/ 0 赞/ 170 阅读

相关 HDU 1253(BFS)

题意：如题。 include <iostream> include <string> include <cstring> include

Dear 丶/ 2022年09月20日 12:35/ 0 赞/ 138 阅读

相关 HDU 1240(bfs)

题意：给出一个三维空间，宇宙飞船的起始地点，目标地点，求最短飞行距离。 include <iostream> include <str

红太狼/ 2022年09月20日 11:28/ 0 赞/ 128 阅读

相关 HDU 1195(bfs)

题意：如题。 include <iostream> include <cstring> include <string> incl

我就是我/ 2022年09月20日 11:25/ 0 赞/ 164 阅读

相关 HDU 1180(bfs)

题意：如题。 include <iostream> include <string> include <sstream> incl

灰太狼/ 2022年09月20日 11:25/ 0 赞/ 150 阅读

相关 HDU 1728(BFS)

问题描述: 给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些

约定不等于承诺〃/ 2022年06月08日 12:25/ 0 赞/ 188 阅读

相关 HDU 1372 Knight Moves——————BFS , 优先队列

Knight Moves Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java

缺乏、安全感/ 2022年05月14日 11:41/ 0 赞/ 173 阅读

相关 hdu 1372(simple BFS)

[Problem link adress:click here][Problem link adress_click here] This is a basic BFS pr

水深无声/ 2021年12月11日 11:29/ 0 赞/ 183 阅读

相关 [HDU 1372] Knight Moves

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1372 题目描述：在一个棋盘中，给你两个点的坐标，同时，你有八种走法，当然

港控/mmm°/ 2021年09月29日 03:34/ 0 赞/ 230 阅读

相关 HDU 1372 Knight Moves 题解

Knight Moves Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

本是古典何须时尚/ 2021年09月20日 08:08/ 0 赞/ 230 阅读