题目大意是在一个网格中(行编号从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; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 937题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 850题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 758题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 883题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1679题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1089题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 905题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 731题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 688题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 801题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 634题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1180题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 919题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 694题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 912题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 820题目:http://uva.onlinejudge ... -
UVa 784 Maze Exploration
2012-08-11 14:09 881题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 788题目:http://uva.onlinejudge.org/i ...
相关推荐
### 北大ACM 1915 Knight Moves C++语言源代码解析 #### 背景介绍 在本题目中,“北大 ACM JudgeOnline poj1915 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. ...
【北大POJ2243Knight Moves】是一个典型的图论问题,主要涉及到国际象棋中的马(Knight)的移动规则以及最短路径的计算。在国际象棋中,马每一步可以向前后各跳两格,然后横向或纵向跳一格,形成一个“L”形的移动...
因子:因子也叫因数,例如3*5=15,那么3和5是15的因子。同时15*1=15,那么1和15也是15的因子。 1,3,5,15 这四个因子是15的所有因子。 完数:如果一个数等于不含它本身的其他因子之和,则称该数为‘完数’。...
标题“knightmoves”可能指的是一个与国际象棋或编程挑战相关的项目,因为“knight moves”在象棋中指的是马走动的方式,其移动呈L形。在编程领域,这可能是一个练习,要求用户编写代码来模拟马在棋盘上的移动。结合...
moves = { { 2 , 1 }, { 1 , 2 }, { - 1 , 2 }, { - 2 , 1 }, { - 2 , - 1 }, { - 1 , - 2 }, { 1 , - 2 }, { 2 , - 1 }}; Queue q = new LinkedList<> (); q . add( new int []{ 0 , 0 }); Set< String > ...
printf("To get from %s to %s takes %d knight moves.\n", s1, s2, Astar()); } return 0; } ``` 主函数中,通过不断读取输入来获取起点和终点,并调用 A* 算法求解。如果起点与终点相同,则直接输出 0 步。 综...
Create React App入门 该项目是通过引导的。 可用脚本 在项目目录中,可以运行: npm start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何...
#### 标题解析:“Making the Right Moves” 此书名为《Making the Right Moves》(作出正确的决策),旨在为科研工作者提供一套全面而实用的管理指南。它不仅仅局限于学术研究本身,更强调在学术生涯中的各个层面...
基于MOVES模型对西安市机动车排气污染物进行清单计算,对其各类污染物的排放量进行了统计,核算结果对提出具体的机动车管控措施具有非常重要的指导意义。
《Kool Moves》是一款专为动画设计爱好者和专业人士打造的小巧而强大的软件工具。它以其易用性和丰富的功能集在众多动画制作软件中脱颖而出。在本文中,我们将深入探讨这款软件的特点、功能以及如何利用它来创建出令...
《kool moves》是一款专为游戏动画播放设计的专业软件,其功能强大且支持多种格式,使得用户能够流畅地查看和管理各种游戏动画。这款软件在游戏开发和设计领域有着广泛的应用,深受用户喜爱。 首先,我们要了解的是...
题目很全,包括: Problem A【一本通基础广度优先搜索】细胞 Problem B【一本通基础广度优先搜索】 最少步数 Problem C【一本通基础广度优先搜索】The Castle ...Problem L【一本通基础广度优先搜索】Knight Moves
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
【TV-MOVES】是一个与电视电影相关的项目,但没有提供具体的细节,所以我们将基于一般性的电视和电影行业的知识进行探讨。在这个行业中,涉及到的技术、工具和流程是多方面的,包括内容创作、后期制作、分发和播放等...
移动调制 v0.5 轻量级网络应用程序使用来自 Moves 应用程序 ( ) 的数据来显示自安装 Moves 以来的步行(以及很快跑步和骑自行车)的图表,并为接下来的几天提出建议。 要设置实例,需要移动开发者帐户( ) 重定向 ...
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...