题目链接:hdu 4584 Building bridges
题目大意:给出一张图,图由‘H',’O'和‘C'组成,找到哈夫曼距离最小的’H'和‘C',即所有的’H'和‘C'中哈夫曼距离最小的那对,如果相同按照’H'的行坐标、列坐标、‘C’的行坐标、列坐标输出。
解题思路:暴力搜索,现将所有的H和C分别处理出来,然后暴力枚举。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int N = 50;
const int M = 2005;
const int INF = 0x3f3f3f3f;
struct state {
int x, y;
}c[M], h[M];
int n, m, cntC, cntH;
char s[N];
void init () {
cntC = cntH = 0;
for (int i = 0; i < n; i++) {
scanf("%s", s);
for (int j = 0; j < m; j++) {
if (s[j] == 'C') {
c[cntC].x = i;
c[cntC].y = j;
cntC++;
} else if (s[j] == 'H') {
h[cntH].x = i;
h[cntH].y = j;
cntH++;
}
}
}
}
inline int Count (int a, int b) {
return abs(h[a].x - c[b].x) + abs(h[a].y - c[b].y);
}
bool cmp (const state& a, const state& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
void solve () {
int ans = INF, ansC, ansH;
sort (c, c + cntC, cmp);
sort (h, h + cntH, cmp);
for (int i = 0; i < cntH; i++) {
for (int j = 0; j < cntC; j++) {
int d = Count(i, j);
if (d < ans) {
ans = d;
ansH = i;
ansC = j;
}
}
}
printf("%d %d %d %d\n", h[ansH].x, h[ansH].y, c[ansC].x, c[ansC].y);
}
int main () {
while (scanf("%d%d", &n, &m) == 2 && n && m) {
init ();
solve ();
}
return 0;
}
分享到:
相关推荐
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
搜索 dfs 解题代码 hdu1241
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码