题目链接: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;
}
分享到:
相关推荐
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
zoj 3590 -3+1.md
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]
zoj 2536 这个不是用贪心做的
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
NULL 博文链接:https://weitch.iteye.com/blog/1006774
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ1805代码
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复