codeforces 3A Shortest path of the king

72 阅读 0 评论 48 点赞

我是靠谱客的博主迅速大船，最近开发中收集的这篇文章主要介绍codeforces 3A Shortest path of the king，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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.

$\text{[math]}$

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 1to 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.

题目的大意是，给定一个国王的起点和终点，求国王从起点到终点的最短路径。（国王每次只能移动到周围的8个格子之一）

这个就是很简单的贪心了。

1.求出x方向的位移dx

2.求出y方向的位移dy

3.先走min(abs(dx), abs(dy))步斜的

4.走max(abs(dx), abs(dy)) - min(abs(dx), abs(dy))步直的

5.反正就是很简单的了.实在不行,像我一样多写几个if就好

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <stack>
#include <map>
using namespace std;
struct pt {
int x;
int y;
};
int ma(int a, int b) {
return a > b ? a : b;
}
int mi(int a, int b) {
return a < b ? a : b;
}
int main() {
char p[3];
pt start;
scanf("%s", p);
start.x = p[0] - 'a';
start.y = p[1] - '1';
pt end;
scanf("%s", p);
end.x = p[0] - 'a';
end.y = p[1] - '1';
int dx = end.x - start.x;
int dy = end.y - start.y;
if (dx >= 0 && dy >= 0) {
printf("%dn", ma(dx, dy));
for (int i = 0; i < mi(dx, dy); i++) printf("RUn");
for (int i = mi(dx, dy); i < ma(dx, dy); i++) printf("%sn", dx == ma(dx, dy) ? "R" : "U");
} else if (dx < 0 && dy < 0) {
dx *= -1;
dy *= -1;
printf("%dn", ma(dx, dy));
for (int i = 0 ; i < mi(dx, dy); i++) printf("LDn");
for (int i = mi(dx, dy); i < ma(dx, dy); i++) printf("%sn", dx == ma(dx, dy) ? "L" : "D");
} else if (dx >= 0 && dy < 0) {
dy *= -1;
printf("%dn", ma(dx, dy));
for (int i = 0; i < mi(dx, dy); i++) printf("RDn");
for (int i = mi(dx, dy); i < ma(dx, dy); i++) printf("%sn", dx == ma(dx, dy) ? "R" : "D");
} else {
dx *= -1;
printf("%dn", ma(dx, dy));
for (int i = 0; i < mi(dx, dy); i++) printf("LUn");
for (int i = mi(dx, dy); i < ma(dx, dy); i++) printf("%sn", dx == ma(dx, dy) ? "L" : "U");
}
return 0;
}