Shortest Path of the King CodeForces #3A 题解[C++]

57 阅读 0 评论 38 点赞

我是靠谱客的博主娇气高跟鞋，最近开发中收集的这篇文章主要介绍Shortest Path of the King CodeForces #3A 题解[C++]，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来源

http://codeforces.com/contest/3/problem/A

题意解析

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.
chessboard

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).

Examples
input

a8 h1

output

7
RD
RD
RD
RD
RD
RD
RD

给出一个上图所示的棋盘, 棋盘上现有孤王一只. 输入它目前的位置 s, 和目的地 t, 求出s->t的最短路长度和最短路各节点. 棋盘上的坐标用 “a1”, “h8”这样的点来表示.

解题思路

水题. 直接用贪心算法求解即可. 容易看到, 在王能走的八个方向中, 也就是说在王下一步可能到达的八个点中, 只可能有一个点距离目的地有最短距离. 我们找出它来直接作为下一跳即可. 每一跳都选择最优选择, 那么容易看出, 最后得出的路径必然是最短路径.

代码实现

#include <iostream>
#include <queue>
using namespace std;
typedef pair<char, int> point;
pair<int, int> dir[8] = { make_pair(-1,1),make_pair(0,1),make_pair(1,1),make_pair(1,0),make_pair(1,-1),make_pair(0,-1),make_pair(-1,-1),make_pair(-1,0) };
char* Dir[8] = { "LU","U","RU","R","RD","D","LD","L"};
int main()
{
point s, t;
scanf("%c%d%c%c%d", &s.first, &s.second, &t.first, &t.first, &t.second);
s.second--;
t.second--;
point temp = s;
int nextHop,minDis,tempDis,ret = 0;
queue<int> paths;
while (temp!=t) {
minDis = INT_MAX;
for (int i = 0; i < 8; i++) {
if (temp.first + dir[i].first >= 'a'&&temp.first + dir[i].first <= 'h'
&&temp.second + dir[i].second >= 0 && temp.second + dir[i].second <= 7
&& (tempDis = (temp.first + dir[i].first - t.first)*(temp.first + dir[i].first - t.first)
+ (temp.second + dir[i].second - t.second)*(temp.second + dir[i].second - t.second))
< minDis) {
minDis = tempDis;
//printf("MinDIs %dn", minDis);
nextHop = i;
}
}
temp.first += dir[nextHop].first;
temp.second += dir[nextHop].second;
paths.push(nextHop);
//printf("%c%dn", temp.first, temp.second);
ret++;
}
printf("%dn", ret);
while (!paths.empty()) {
printf("%sn", Dir[paths.front()]);
paths.pop();
}
//system("PAUSE");
return 0;
}