글 읽기 - 63% 쯤에서 틀릴 때 참고사항

tkdgus0782 5일 전 0

큐로 구현하던 중, 0이 나올때까지만 맵을 순회해서 구슬을 저장하는 식으로 짜면 63%즈음에서 틀리네요..
처음 주어지는 구슬에 빈 칸이 있을 수 있습니다.
혹여나 비슷하게 구현하신 분 있을실까해서 글 올려봅니다.
//구현하던거 저장

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

#define vi vector<int>
#define vc vector<char>
#define pii pair<int, int>

//n은 홀수
//상어는 중앙에있다.
//구슬은 1,2,3이 있으며, 같은 수의 구슬이 연속하는 번호에 있다면 연속하는 구슬이다.
// 1
//마법은 방향d와 거리 s가있고, 상하좌우 1~4 범위이다.
//해당 방향의 거리 안쪽의 모든 구슬을 파괴하고, 그 칸은 빈칸이 된다.
// 2
//구슬이 파괴되면 모든 구슬이 숫자가 작은쪽으로 이동한다(모든 구슬이 움직이지 않을때까지)
//연속하는 구슬이 4개 이상으로 구성되면 폭발한다.
//폭발/이동이 번갈아 일어나며, 아무일이 없을때까지 반복된다.
//3
//연속하는 구슬들은 2개의구슬로 변화한다. 
//그룹 a는 그룹의 구슬 개수이고, B는 그룹을 이루는 구슬의 개수이다.
//구슬은 그룹의 순서대로 1번칸부터 차례로 A,B의 순서로 들어간다
//4개 이상인 것들은 이미 폭발햇을거니까, 무조건 1~3이 된다 이말이지
//구슬이 칸의 수보다 많다면 그 구슬들은 사라진다

//최종 점수 = (폭발한 A번 구슬 * A) //문제 보니까 마법쓴건 파괴인듯?

//이거 소용돌이 순서를 어떻게 계산해야하지..
//일단 왼쪽, 아래, 오른쪽, 위 순서대로 1씩늘어나는 거리로 가니까 그렇게 순회해도되고..
//순회는 그렇게하고, 구슬 처리는 큐로 하는게 좋아보이네 ㅇㅈ?

//마법쓰면 arr에서 값 수정해서 0으로 바꾸고
//순회한번해서 큐에 다넣어
//큐에서 하나씩 빼가면서 중복구슬 그룹 처리 다해주고
//마지막에 arr에 넣으면서 변화구슬처리 하기

//아니면 애초에 arr쓰지 않고, 마법쓸 때에만 idx계산하기


//위 9-2, 25-3, 49-4
//아 4-1, 16-2, 36-3
//왼 1, 9+1, 25+2
//오 4+1, 16+2, 36+3

int dirs[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

vi magic(int d, int s) {
    vi result;

    if (d == 1) {
        for (int i = 0; i < s; i++) {
            int next = (2 * i + 3) * (2 * i + 3) - i - 2;
            result.push_back(next);
        }
    }
    else if (d == 2) {
        for (int i = 0; i < s; i++) {
            int next = (2 * i + 2) * (2 * i + 2) - i - 1;
            result.push_back(next);
        }
    }
    else if (d == 3) {
        for (int i = 0; i < s; i++) {
            int next = (2 * i + 1) * (2 * i + 1) + i;
            result.push_back(next);
        }
    }
    else if (d == 4) {
        for (int i = 0; i < s; i++) {
            int next = (2 + i * 2) * (2 + i * 2) + i + 1;
            result.push_back(next);
        }
    }

    return result;
}

queue<int> search(vector<vi> arr, int shark ) {
    int ny, nx;
    ny = nx = shark - 1;

    int len = arr.size();

    int d = 1, cnt = 0, idx = 0;

    queue<int> balls;

    //소용돌이 순회
    while (idx < len*len - 1) {
        for (int i = 0; i < d; i++) {
            ny += dirs[cnt][1];
            nx += dirs[cnt][0];
            if(arr[ny][nx] != 0)
                balls.push(arr[ny][nx]);
            idx++;
        }
        cnt = (cnt + 1) % 4;

        for (int i = 0; i < d; i++) {
            ny += dirs[cnt][1];
            nx += dirs[cnt][0];
            if (arr[ny][nx] != 0)
                balls.push(arr[ny][nx]);
            idx++;
        }
        cnt = (cnt + 1) % 4;
        
        if (d + idx == len * len - 1) {
            //마지막 줄
            for (int i = 0; i < d; i++) {
                ny += dirs[cnt][1];
                nx += dirs[cnt][0];
                if (arr[ny][nx] != 0)
                    balls.push(arr[ny][nx]);
                idx++;
            }
        }
        else {
            d++;
        }
    }
    return balls;
}

bool destroyed(vi& arr, int b) {
    for (auto k : arr) {
        if (k == b)
            return true;
    }
    return false;
}

void check_q(queue<int> q) {
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
}

//1.마법 시전
void blizzard(queue<int> &balls, int d, int s) {
    vi dest = magic(d, s);
    queue<int> tmp;

    int cnt = 0;//원본 번호
  
    while (!balls.empty()) {
        cnt++;
        int ball = balls.front(); balls.pop();

        if (destroyed(dest, cnt)) {
            continue;
        }

        tmp.push(ball);
    }

    balls = tmp;
}

bool explosion(queue<int>& balls, vi &score) {
    queue<int> tmp;
    bool changed = false;

    int bef;
    if (!balls.empty())
        bef = balls.front();
    else
        return changed;

    int cnt = 0;//연속 개수

    while (!balls.empty()) {
        int ball = balls.front(); 
        if (ball == bef) {//연속 구슬 그룹
            cnt++;
            balls.pop();
        }
        else if (cnt >= 4) {//폭발
            score[bef - 1] += cnt;
            cnt = 0;
            changed = true;
        }
        else {//연속 아니므로 큐에 삽입
            for (int i = 0; i < cnt; i++) {
                tmp.push(bef);
            }
            cnt = 0;
        }
        bef = ball;
    }

    if (0 < cnt && cnt < 4) {//연속 아니므로 큐에 삽입
        for (int i = 0; i < cnt; i++) {
            tmp.push(bef);
        }
    }
    else if (cnt >= 4) {//폭발
        score[bef - 1] += cnt;
        cnt = 0;
        changed = true;
    }
    balls = tmp;
    return changed;
}

void change(queue<int>& balls, int thres) {

    queue<int>tmp;

    int amount = 0;//구슬의 개수

    int before;
    if (!balls.empty())
        before = balls.front();
    else
        return;

    int cnt = 0;
    while (!balls.empty()) {
        int now = balls.front();

        if (now == before) {
            cnt++;
            balls.pop();
        }
        else {
            if (amount < thres) {//그룹 a
                tmp.push(cnt); 
                amount++;
            }
            if (amount < thres) {//그룹 b
                tmp.push(before);
                amount++;
            }
            cnt = 0;
        }
        before = now;
    }

    if (amount < thres) {
        tmp.push(cnt);
        amount++;
    }
    if (amount < thres) {
        tmp.push(before);
        amount++;
    }

    balls = tmp;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;//m은 블리자드 마법 시전 횟수

    cin >> n >> m;

    int shark = (n + 1) / 2;//x,y동일
    vector<vi> arr(n, vi(n, 0));
    queue<int> ball;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    //초기 공 찾아서 큐에 넣기
    queue<int> balls = search(arr, shark);
    vi score(3, 0);//폭발한 구슬 수
    int threshold = n * n - 1;//구슬 최대 수
    //cout << "{" << threshold << "}\n";

    for (int i = 0; i < m; i++) {
        int d, s;
        cin >> d >> s;

        //1.마법시전
        blizzard(balls, d, s);
        
        //2.구슬 폭발
        while (explosion(balls, score));
        

        //3.구슬 변화
        change(balls, threshold);
    }

    int result = 0;
    for (int i = 0; i < 3; i++) {
        result += score[i] * (i + 1);
    }
    cout << result;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

63% 쯤에서 틀릴 때 참고사항

tkdgus0782 5일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
