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;
}

Azure99

底层码农,休闲音游玩家,偶尔写写代码

看看这些?

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注