`
Jianquan
  • 浏览: 19634 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

Uva 439 Knight Moves

    博客分类:
  • UVa
阅读更多

题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380

题目大意是在一个网格中(行编号从1~8,列编号从a~h),给你两个点,要你找出象棋中的马从一个点跳到另一个点的最少步数。是一道十分基础的bfs(宽度优先搜索)。

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;

struct Point
{
	int x,y,step;
	bool operator == (const Point &b)
	{
		if(x==b.x&&y==b.y) return 1;
		else return 0;
	}
};
int bfs(Point a,Point b)
{
	queue<Point> q;
	if(a==b) return 0;
	q.push(a);
	while(!q.empty())
	{
		Point cur=q.front();
		q.pop();
		if(cur==b) return cur.step;
		int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};//马跳跃的八个方向
		for(int i=0;i<8;i++)
		{
			Point next;
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			next.step=cur.step+1;
			if(next.x<1||next.x>8||next.y<1||next.y>8) continue;//判断越界
			q.push(next);
		}
	}
	return -1;//马一定可以跳到终点,所以这只是一个形式
}
int main()
{
	string str1,str2;
	Point a,b;
	while(cin>>str1>>str2)
	{
		a.y=str1[0]-'a'+1;//先把字母转换成数字
		a.x=str1[1]-'0';
		a.step=0;
		b.y=str2[0]-'a'+1;
		b.x=str2[1]-'0';
		int ans=bfs(a,b);
		cout<<"To get from "<<str1<<" to "<<str2<<" takes "<<ans<<" knight moves."<<endl;
	}
	return 0;
}

 

分享到:
评论

相关推荐

    北大acm 1915 Knight Moves C++语言源代码

    ### 北大ACM 1915 Knight Moves C++语言源代码解析 #### 背景介绍 在本题目中,“北大 ACM JudgeOnline poj1915 Knight Moves”要求解决的是一个经典的骑士行走问题。具体来说,题目背景提到了一位自称无人能及的...

    北大POJ2243Knight Moves

    【北大POJ2243Knight Moves】是一个典型的图论问题,主要涉及到国际象棋中的马(Knight)的移动规则以及最短路径的计算。在国际象棋中,马每一步可以向前后各跳两格,然后横向或纵向跳一格,形成一个“L”形的移动...

    Knight Moves

    Your task is to write a program to calculate the minimum number of moves移动次数 needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov. ...

    Knight Moves.txt

    因子:因子也叫因数,例如3*5=15,那么3和5是15的因子。同时15*1=15,那么1和15也是15的因子。 1,3,5,15 这四个因子是15的所有因子。 完数:如果一个数等于不含它本身的其他因子之和,则称该数为‘完数’。...

    knightmoves

    标题“knightmoves”可能指的是一个与国际象棋或编程挑战相关的项目,因为“knight moves”在象棋中指的是马走动的方式,其移动呈L形。在编程领域,这可能是一个练习,要求用户编写代码来模拟马在棋盘上的移动。结合...

    knight problem问题c++代码

    printf("To get from %s to %s takes %d knight moves.\n", s1, s2, Astar()); } return 0; } ``` 主函数中,通过不断读取输入来获取起点和终点,并调用 A* 算法求解。如果起点与终点相同,则直接输出 0 步。 综...

    KnightMoves

    Create React App入门 该项目是通过引导的。 可用脚本 在项目目录中,可以运行: npm start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何...

    Making the Right Moves

    #### 标题解析:“Making the Right Moves” 此书名为《Making the Right Moves》(作出正确的决策),旨在为科研工作者提供一套全面而实用的管理指南。它不仅仅局限于学术研究本身,更强调在学术生涯中的各个层面...

    leetcode棋盘-minimum-knight-moves:最小骑士移动

    moves = { { 2 , 1 }, { 1 , 2 }, { - 1 , 2 }, { - 2 , 1 }, { - 2 , - 1 }, { - 1 , - 2 }, { 1 , - 2 }, { 2 , - 1 }}; Queue q = new LinkedList&lt;&gt; (); q . add( new int []{ 0 , 0 }); Set&lt; String &gt; ...

    基于MOVES模型的西安市机动车排放清单研究_郝艳召.caj

    基于MOVES模型对西安市机动车排气污染物进行清单计算,对其各类污染物的排放量进行了统计,核算结果对提出具体的机动车管控措施具有非常重要的指导意义。

    Kool Moves

    《Kool Moves》是一款专为动画设计爱好者和专业人士打造的小巧而强大的软件工具。它以其易用性和丰富的功能集在众多动画制作软件中脱颖而出。在本文中,我们将深入探讨这款软件的特点、功能以及如何利用它来创建出令...

    kool moves

    《kool moves》是一款专为游戏动画播放设计的专业软件,其功能强大且支持多种格式,使得用户能够流畅地查看和管理各种游戏动画。这款软件在游戏开发和设计领域有着广泛的应用,深受用户喜爱。 首先,我们要了解的是...

    C++广度优先搜索一本通习题

    题目很全,包括: Problem A【一本通基础广度优先搜索】细胞 Problem B【一本通基础广度优先搜索】 最少步数 Problem C【一本通基础广度优先搜索】The Castle ...Problem L【一本通基础广度优先搜索】Knight Moves

    moves:Moves 的 Ruby 客户端

    moves = Moves :: Client . new ( access_token ) 获取个人资料 moves . profile 获取每日总结 moves . daily_summary # current day moves . daily_summary ( "2013-06-20" ) # any day moves . daily_summary...

    engine-value_moves.c

    engine-value_moves.c

    TV-MOVES

    【TV-MOVES】是一个与电视电影相关的项目,但没有提供具体的细节,所以我们将基于一般性的电视和电影行业的知识进行探讨。在这个行业中,涉及到的技术、工具和流程是多方面的,包括内容创作、后期制作、分发和播放等...

    move-modulate:Moves 应用程序的 Web 界面,通过推荐调整用户的后续活动

    移动调制 v0.5 轻量级网络应用程序使用来自 Moves 应用程序 ( ) 的数据来显示自安装 Moves 以来的步行(以及很快跑步和骑自行车)的图表,并为接下来的几天提出建议。 要设置实例,需要移动开发者帐户( ) 重定向 ...

    WPF 国际象棋 棋子 ChessProgrammingTest.zip

    You have been provided with a third-party library "ChessLib" which calculates the legal moves a knight can make given a position on an 8 by 8 board. The library has been used to create a program which...

Global site tag (gtag.js) - Google Analytics