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。

思路

比赛时我发现这是三个难度不同的题，于是就直接开了最难的。

1. 输入Bug，用两个数组，一个保存Bugs，一个保存周围有Bugs的点
2. 建图，用点的坐标指向点的下标
3. 然后每输入一个Bug，就给周围+1
4. 最后排序输出，注意: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;
}