SDNUOJ-1235-及及debug
题目
Description 及及是热爱写代码,可是因为他太菜了每次出现很多bug,于是他每天都debug到很晚而且很累很累。某一天在他结束了一天debug之后倒头就睡,当他醒来的时候发现自己置身一个bug世界,bug世界有p*q(p行q列)个格子组成,有n个bug分布在这p*q个格子中。 可是及及好累(cai)啊,他这次不能解决这些bug了,于是他想到来标记这些bug,在每个格子中填入一个数字来代表周围8个格子中bug的个数,及及觉得这个任务太简(kun)单(nan)了,于是让你来做,你能帮他标记好bug,然后将bug提示不为0的坐标和bug提示以及bug的位置告诉及及吗?(具体看下面的解释) Input 输入包含多组测试样例。每组测试样例: 第一行一个整数 n (0 <= n <= 1000) 代表bug的个数。 第二行两个整数 p q (0 <= p, q <= 10000000000) 代表bug世界的大小。 接下来 n 行每行两个整数 Xi Yi (0 <= Xi < p, 0 <= Yi < q) 代表bug的位置。 Output 对每组样例:第一行输出“Case #x:” 其中x代表当前为第几组测试样例。 接下来输出提示部分,每一行三个整数 (先按提示大小降序然后再按行坐标升序最后按列坐标升序排列) 提示的行坐标 提示的列坐标 提示大小 例如:1 2 1 接下来输出bug部分,每一行两个整数 (先按行坐标升序再按列坐标升序排列) bug的行坐标 bug的列坐标 例如:1 1 bug周围的bug不需要在提示中输出。 每组测试样例之间用一个空行隔开。
样例
Sample Input
1
9 9
0 0
Sample Output
Case #1:
0 1 1
1 0 1
1 1 1
0 0
题目分析
题意
大模拟,给你一张二维地图的大小和Bugs(点),让你按要求排序输出周围有Bugs的点和Bugs。
思路
比赛时我发现这是三个难度不同的题,于是就直接开了最难的。
- 输入Bug,用两个数组,一个保存Bugs,一个保存周围有Bugs的点
- 建图,用点的坐标指向点的下标
- 然后每输入一个Bug,就给周围+1
- 最后排序输出,注意:Tip中可能有点的坐标为Bug,这些不予输出
代码
#include <iostream> #include <cstdio> #include <cstring> #include <map> #include <vector> #include <algorithm> using namespace std; typedef pair<long long, long long> Loc; struct Tip { Loc l; int cnt; }; Loc Bugsv[1010]; Tip Tipsv[9010]; int Tipcnt = 1; map<Loc, int> tipm; map<Loc, bool> ex; bool cmp(Tip A, Tip B) { if (A.cnt == B.cnt) { if (A.l.first == B.l.first) return A.l.second < B.l.second; return A.l.first < B.l.first; } else { return A.cnt > B.cnt; } } bool cmp2(Loc A, Loc B) { if (A.first == B.first) return A.second < B.second; return A.first < B.first; } int main() { int T, Case = 1; bool f = false; while (scanf("%d", &T) != EOF) { Tipcnt = 1; memset(Bugsv, 0, sizeof(Bugsv)); memset(Tipsv, 0, sizeof(Tipsv)); tipm.clear(); ex.clear(); long long N, M; scanf("%lld %lld", &N, &M); //下标从1开始 for (int Ti = 1; Ti <= T; Ti++) { long long x, y; scanf("%lld %lld", &x, &y); Bugsv[Ti].first = x; Bugsv[Ti].second = y; ex[Loc(x, y)] = true; for (int i = -1; i <= 1; i++) { for (int i2 = -1; i2 <= 1; i2++) { if (i == 0 && i2 == 0) continue; long long newx = x + i; long long newy = y + i2; if (newx >= 0 && newx < N && newy >= 0 && newy < M) { if (tipm[Loc(newx, newy)] == 0) { tipm[Loc(newx, newy)] = Tipcnt; Tipsv[Tipcnt].l = Loc(newx, newy); Tipsv[Tipcnt].cnt = 1; Tipcnt++; } else { int ID = tipm[Loc(newx, newy)]; Tipsv[ID].cnt++; } } } } } sort(Tipsv + 1, Tipsv + Tipcnt, cmp); if (f) { printf("\n"); } else { f = true; } printf("Case #%d:\n", Case++); for (int i = 1; i < Tipcnt; i++) { if (!ex[Loc(Tipsv[i].l.first, Tipsv[i].l.second)]) { printf("%lld %lld %d\n", Tipsv[i].l.first, Tipsv[i].l.second, Tipsv[i].cnt); } } sort(Bugsv + 1, Bugsv + T + 1, cmp2); for (int i = 1; i <= T; i++) { printf("%lld %lld\n", Bugsv[i].first, Bugsv[i].second); } } return 0; }