HDU 4584（2013杭州邀请赛I题-水）

本文主要是介绍HDU 4584（2013杭州邀请赛I题-水），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4584

题意：找出一条HC路线，要求HC的曼哈顿距离尽量小，H的x坐标尽量小，y坐标尽量小，C的x坐标尽量小，y坐标尽量小。

思路：直接在每条边去找出答案即可，我是直接排个序就找出答案。

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int N = 1605;struct Point {int x, y;Point(){}Point(int _x, int _y) {x = _x; y = _y;}
} c[N], h[N];struct Edge {int dis;Point a, b;Edge() {}Edge(Point _a, Point _b) {a = _a; b = _b;dis = abs(a.x - b.x) + abs(a.y - b.y);}
} e[666666];
int n, m, cn, hn, en;
char str[45];bool cmp(Edge a, Edge b) {if (a.dis != b.dis)return a.dis < b.dis;if (a.a.x != b.a.x)return a.a.x < b.a.x;if (a.a.y != b.a.y)return a.a.y < b.a.y;if (a.b.x != b.b.x)return a.b.x < b.b.x;return a.b.y < b.b.y;
}int main() {while (~scanf("%d%d", &n, &m) && n + m) {cn = hn = en = 0;for (int i = 0; i < n; i++) {scanf("%s", str);for (int j = 0; j < m; j++) {if (str[j] == 'C')c[cn++] = Point(i, j);else if (str[j] == 'H')h[hn++] = Point(i, j);}}for (int i = 0; i < hn; i++) {for (int j = 0; j < cn; j++) {e[en++] = Edge(h[i], c[j]);}}sort(e, e + en, cmp);printf("%d %d %d %d\n", e[0].a.x, e[0].a.y, e[0].b.x, e[0].b.y);}return 0;
}

这篇关于HDU 4584（2013杭州邀请赛I题-水）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---