글 읽기 - 놓친 부분이 있는지 도와주실 분 찾습니다..!

senitf 2년 전 1

가능한 최고점을 찾고 (scan)

최고점을 기록했던 인덱스를 시작으로 사용했던 블럭들을 지우고, (scanDel)

중력 작용(gravity)

회전(spin)

중력 작용(gravity)

순서로 구현했습니다. 채점 시작과 동시에 틀려서 중요한 부분을 간과하고 푼 것 같습니다..

혹시 도와주실분 계실까요..?

코드에 주석 추가했습니다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
struct move{
    int x, y;
};
struct move mv[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<p> q;
int N, M, arr[22][22], delX, delY;
int scan(){
    int i, j, k, target, tmpAns, ans = 1, curX, curY, nxtX, nxtY, tmpRain, rain = 0;
    for(i = 1; i <= N; i++){
        for(j = 1; j <= N; j++){
            if(arr[i][j] > 0){
                bool visit[22][22] = {0};
                target = arr[i][j];
                q.push(make_pair(i, j));
                visit[i][j] = true;
                tmpAns = 1;
                tmpRain = 0;
                while(!q.empty()){ //탐색
                    curY = q.front().first;
                    curX = q.front().second;
                    q.pop();
                    for(k = 0; k < 4; k++){
                        nxtY = curY + mv[k].y;
                        nxtX = curX + mv[k].x;
                        if(nxtX >= 1 && nxtX <= N && nxtY >= 1 && nxtY <= N){
                            if(visit[nxtY][nxtX] == false){
                                if(arr[nxtY][nxtX] == 0 || arr[nxtY][nxtX] == target){ //가능한 범위 내에서 방문하지 않았고, 무지개 또는 시작 블럭의 값과 같은 경우
                                    q.push(make_pair(nxtY, nxtX));
                                    visit[nxtY][nxtX] = true; //방문 표시
                                    tmpAns++; //점수 계산
                                    if(arr[nxtY][nxtX] == 0)
                                        tmpRain++; //무지개 블럭의 수를 카운트
                                }
                            }
                        }
                    }
                }
                if(ans < tmpAns){
                    ans = tmpAns;
                    delY = i;
                    delX = j;
                    rain = tmpRain;
                } //기존의 점수보다 높게 나온 경우 바로 기록
                else if(ans == tmpAns){
                    if(rain <= tmpRain){
                        ans = tmpAns;
                        delY = i;
                        delX = j;
                        rain = tmpRain;
                    }
                } //기존의 점수와 동일한 경우 무지개 블럭의 수를 비교
            }
        }
    }
    return ans;
}
void scanDel(){
    int curX, curY, nxtX, nxtY, target, i;
    bool visit[22][22] = {0};
    target = arr[delY][delX];
    q.push(make_pair(delY, delX));
    visit[delY][delX] = true;
    arr[delY][delX] = -2;
    while(!q.empty()){ //scan 과 같은 방식으로 탐색 후 -2 로 표시해 블럭 삭제
        curY = q.front().first;
        curX = q.front().second;
        q.pop();
        for(i = 0; i < 4; i++){
            nxtY = curY + mv[i].y;
            nxtX = curX + mv[i].x;
            if(nxtX >= 1 && nxtX <= N && nxtY >= 1 && nxtY <= N){
                if(visit[nxtY][nxtX] == false){
                    if(arr[nxtY][nxtX] == 0 || arr[nxtY][nxtX] == target){
                        q.push(make_pair(nxtY, nxtX));
                        visit[nxtY][nxtX] = true;
                        arr[nxtY][nxtX] = -2;
                    }
                }
            }
        }
    }
}
void spin(){
    int i, j, copy[22][22];
    for(i = 1 ; i <= N; i++){
        for(j = 1; j <= N; j++){
            copy[i][j] = arr[i][j];
        }
    }
    for(i = 1 ; i <= N; i++){
        for(j = 1; j <= N; j++){
            arr[N - j + 1][i] = copy[i][j];
        }
    } //배열을 복사하여 spin 결과에 맞게 입력
}
void gravity(){
    int i, j, swapY, tmp;
    for(i = N; i >= 1; i--){
        for(j = 1; j <= N; j++){
            if(arr[i][j] >= 0){
                swapY = i + 1;
                while(arr[swapY][j] == -2){
                    swapY++;
                }
                swapY -= 1;
                tmp = arr[swapY][j];
                arr[swapY][j] = arr[i][j];
                arr[i][j] = tmp;
            }
        }
    } //무지개, 일반 블럭의 경우 -2, 빈칸을 지나는 동안 인덱스를 증가하여 마지막 인덱스에 해당하는 블럭과 스왑

}
int main(){
    int i, j, ans = 0, tmpAns;
    scanf("%d %d", &N, &M);
    for(i = 1; i <= N; i++){
        for(j = 1; j <= N; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    while(true){
        tmpAns = -1;
        tmpAns = scan();
        if(tmpAns == 1)
            break; //점수가 1인 경우 점수를 낼 블럭이 없음
        scanDel();
        ans += (tmpAns * tmpAns);
        gravity();
        spin();
        gravity();
    }
    printf("%d\n", ans);
}

senitf 2년 전 2

자문자답 입니다

기준 블럭이 행과 열이 가장 작은 일반 블럭을 기준으로 한다는 조건을 간과하였습니다. 관련 코드 한줄 추가하니 바로 통과했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

놓친 부분이 있는지 도와주실 분 찾습니다..!

senitf 2년 전 1

senitf 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말