A. Shortest path of the king
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output
The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.
In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).
Input
The first line contains the chessboard coordinates of square s, the second line — of square t.
Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.
Output
In the first line print n — minimum number of the king's moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD.
L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.
Examples
input
a8
h1
output
7
RD
RD
RD
RD
RD
RD
RD
解题思路:一个8*8的图,8个方向移动,字符转化为数字表示,bfs记录路径最短路径,到达目标点即遍历结束,记录路径,路径移动方向转变为题中的字符方向。
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std;
int d_x[4] = { 0, 1, -1 };
int d_y[4] = { 0, 1, -1 };
int e[10][10], book[10][10];
int next[2][10000];
int end_xx[10000],end_yy[10000];
int sum;
int start_x, start_y, end_x, end_y;
struct node {
int pre;
int x, y;
int step;
};
node qt[10000];
void conversion(int x,int y){
if(x==1){
cout<<"R";
}else if(x==-1){
cout<<"L";
}
if(y==-1){
cout<<"D";
}else if(y==1){
cout<<"U";
}
}
void bfs() {
int head = 1;
int tail = 1;
node q;
q.x = start_x;
q.y = start_y;
q.pre = head;
q.step = 0;
qt[tail] = q;
qt[tail].pre = head;
tail++;
queue<node> qq;
qq.push( q );
while( !qq.empty() ) {
node temp = qq.front();
head = temp.pre;
// cout<<"head = "<<head<<endl;
if( temp.x == end_x && temp.y == end_y ) {
int xx = temp.x;
int yy = temp.y;
sum = 0;
// cout<<"temp.pre = "<<temp.pre<<endl;
int t = qt[temp.pre].pre;
// cout<<"t ="<<t<<endl;
while(true){
// cout<<sum<<endl;
end_xx[sum] = xx-qt[t].x;
end_yy[sum] = yy-qt[t].y;
sum++;
xx = qt[t].x;
yy = qt[t].y;
if(t==1) break;
t = qt[t].pre;
}
break;
}
for(int i=0;i<3;i++){
for(int j =0;j<3;j++){
if(i==0 && j==0) continue;
int dx = temp.x + d_x[i];
int dy = temp.y + d_y[j];
if(dx>8 || dy>8 || dx<1 || dy<1) continue;
if(book[dx][dy]==0 ){
book[dx][dy] = 1;
node tt;
tt.x = dx;
tt.y = dy;
tt.pre = tail;
tt.step = temp.step+1;
qt[tail] = tt;
qt[tail].pre = head;
tail++;
qq.push(tt);
}
}
}
qq.pop();
}
return;
}
int main() {
char start[2];
char end[2];
while(cin>>start[0]>>start[1]>>end[0]>>end[1]){
start_x = start[0]-'a'+1;
start_y = start[1]-'0';
end_x = end[0]-'a'+1;
end_y = end[1]-'0';
// cout<<start_x<<" "<<end_x<<endl;
//
// cout<<start_y<<" "<<end_y<<endl;
if(start_x == end_x && start_y == end_y) {
cout<<"0"<<endl;
continue;
}
memset( book, 0, sizeof( book ) );
book[start_x][start_y] = 1;
bfs();
cout<<sum<<endl;
for( int i = sum-1 ; i >= 0; i-- ) {
// cout<<end_xx[i]<<" "<<end_yy[i]<<endl;
conversion( end_xx[i], end_yy[i] );
cout<<endl;
}
}
return 0;
}
Codeforces-A. Shortest path of the king(简单bfs记录路径)的更多相关文章
-
Codeforces 3A-Shortest path of the king(BFS打印路径)
A. Shortest path of the king time limit per test 1 second memory limit per test 64 megabytes input s ...
-
node搜索codeforces 3A - Shortest path of the king
发一下牢骚和主题无关: 搜索,最短路都可以 每日一道理 人生是洁白的画纸,我们每个人就是手握各色笔的画师:人生也是一条看不到尽头的长路,我们每个人则是人生道路的远足者:人生还像是一块神奇的土地 ...
-
Codeforces Beta Round #3 A. Shortest path of the king 水题
A. Shortest path of the king 题目连接: http://www.codeforces.com/contest/3/problem/A Description The kin ...
-
(简单) POJ 3414 Pots,BFS+记录路径。
Description You are given two pots, having the volume of A and B liters respectively. The following ...
-
Codeforces Beta Round #3 A. Shortest path of the king
标题效果: 鉴于国际棋盘两点,寻求同意的操作,是什么操作的最小数量,在操作过程中输出. 解题思路: 水题一个,见代码. 以下是代码: #include <set> #include < ...
-
A - Shortest path of the king (棋盘)
The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, becaus ...
-
Shortest path of the king
必须要抄袭一下这个代码 The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose h ...
-
Codeforces 938G Shortest Path Queries [分治,线性基,并查集]
洛谷 Codeforces 分治的题目,或者说分治的思想,是非常灵活多变的. 所以对我这种智商低的选手特别不友好 脑子不好使怎么办?多做题吧-- 前置知识 线性基是你必须会的,不然这题不可做. 推荐再 ...
-
CF3A Shortest path of the king
The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, becaus ...
随机推荐
-
Android 采用Layout Inflater创建一个View对象
接着上文<Android ListViewview入门>,本文使用android的Inflater来实现 在layouyt文件夹中新建一个list_item.xml的文件,添加如下代码: ...
-
Delphi中GUID相等检查中经典指针应用
type PGUID = ^TGUID; TGUID = packed record D1: LongWord; D2: Word; D3: Word; D4: array[0..7] of Byte ...
-
(剑指Offer)面试题35:第一个只出现一次的字符
题目: 在字符串中找出第一个只出现1次的字符,如输入“abaccdeff”,则输出b. 思路: 1.暴力遍历 从头开始扫描字符串中的每个字符,当访问某个字符时,取该字符与后面的每个字符相比较,如果没有 ...
-
杭电oj1326 Box of Bricks
Tips:先求出平均数再分别计算各数与平均数的差相加,注意两个测试结果之间要空一行 #include<iostream> using namespace std; int main() { ...
-
Java中使用LocalDate根据日期来计算年龄
Java中和日期直接相关的类有很多,平时最常用到的就是java.util package下面的Date和Calendar,需要用到格式的时候还会用到java.text.SimpleDateFormat ...
-
FFmpeg在Linux下安装编译过程
转载请把头部出处链接和尾部二维码一起转载,本文出自:http://blog.csdn.net/hejjunlin/article/details/52402759 今天介绍下FFmpeg在Linux下 ...
-
springmvc 在非controller下使用@autowired
在SpringMVC框架中,我们经常要使用@Autowired注解注入Service或者Mapper接口,我们也知道,在controller层中注入service接口,在service层中注入其它的s ...
-
# 2019-2020-3 《Java 程序设计》实验一:Java开发环境的熟悉
2019-2020-3 <Java 程序设计>实验一:Java开发环境的熟悉-------1 一.实验要求: 1 建立"自己学号exp1"的目录 2 在"自己 ...
-
BugPhobia进阶篇章:系统架构技术规格
0x01 :开发级需求分析 在开发过程中,团队本身在开发的起始阶段确定了基本的开发级需求分析: 在开发过程中,除了需要满足用户级需求以为,我们还需要针对开发团队的特点,满足一些开发级的需求和约束.作为 ...
-
《HTTP 权威指南》笔记:第十二章 基本认证*
导言 客户端可以通过网络来得到想要的信息,但是有一些信息并不能是对所有人都能看到的,因此必须有一种认证机制.服务器需要通过这种方式来了解用户身份,一旦服务器知道了用户的身份,就可以让用户能够访问请求的 ...