zoj 3761 Easy billiards(建图+贪心+dfs)

题目链接：zoj 3761 Easy billiards

题目大意：在一个平面上，有若干个球，给出球的坐标，每次可以将一个球朝另一个球打过去（只有上下左右），碰到下一个球之后原先的球停下来，然后被撞的球朝这个方向移动，直到有一个球再也撞不到下一个球后，这个球飞出。问说最少平面上剩几个球，并且给出打球的方案。

解题思路：对于每个球，最多有4个边，上下左右，将它与每个方向上最近的那个球相连，方法也很简单，先按照x排序，x相同按照y排序，然后遍历，如果相邻的两个之间x相同，即可相连；y同理。

然后对于每个点进行dfs，将它所有的下一个球打掉后，再打掉当前的球，保证了不会因为中间一个球被先打掉后影响答案。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 2005;
const char sign[4][10] = { "UP", "DOWN", "LEFT", "RIGHT" };
struct point {
	int x, y, id;;
}s[N], t[N];

int n, v[N], rec[N], dir[N], ans;
vector<int> g[N];

bool cmpX(const point& a, const point& b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool cmpY(const point& a, const point& b) {
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

void init () {
	ans = 0;
	memset(v, 0, sizeof(v));
	for (int i = 0; i < n; i++) {
		g[i].clear();

		scanf("%d%d", &s[i].x, &s[i].y);
		s[i].id = i;
		t[i] = s[i];
	}

	sort(t, t + n, cmpX);
	for (int i = 1; i < n; i++) {
		if (t[i-1].x == t[i].x) {
			int p = t[i-1].id, q = t[i].id;
			g[p].push_back(q);
			g[q].push_back(p);
		}
	}

	sort(t, t + n, cmpY);
	for (int i = 1; i < n; i++) {
		if (t[i-1].y == t[i].y) {
			int p = t[i-1].id, q = t[i].id;
			g[p].push_back(q);
			g[q].push_back(p);
		}
	}
}

int link(int p, int q) {
	if (s[p].x == s[q].x) {
		return s[p].y > s[q].y ? 0 : 1;
	} else {
		return s[p].x < s[q].x ? 2 : 3;
	}
}

void dfs(int u, int d) {
	v[u] = 1;

	for (int i = 0; i < g[u].size(); i++) if (v[g[u][i]] == 0) {
		int k = link(u, g[u][i]);
		dfs(g[u][i], k);
	}

	rec[ans] = u;
	dir[ans] = d;
	ans++;
}

void solve () {

	for (int i = 0; i < n; i++) if (v[i] == 0) {
		v[i] = 1;
		for (int j = 0; j < g[i].size(); j++) if (v[g[i][j]] == 0) {
			int k = link(i, g[i][j]);
			dfs(g[i][j], k);
		}
	}

	printf("%d\n", n - ans);
	for (int i = 0; i < ans; i++) {
		int p = rec[i];
		printf("(%d, %d) %s\n", s[p].x, s[p].y, sign[dir[i]]);
	}
}

int main () {
	while (scanf("%d", &n) == 1) {
		init();
		solve();
	}
	return 0;
}