글 읽기 - 19237문제 반례

creativa 3년 전 0

1. pair<int,int>SHARK[][]로 SharkNumber, Left Fragment를 각 배열에 저장하였습니다.

2. int head[]는 shark가 위치함을 나타내기 위해 사용했습니다.

3. chageDir[shark번호][방향][우선순위]을 사용하여 상하좌우를 우선순위대로 순회하도록 하였습니다.

4. while문에서 time을 증가시키며 Shark의 개수(마리)가 1이 될 때 답을 출력하도록 하였습니다.

5. head array를 통해 shark의 현재위치를 옮길 수 있도록 참고하고, Shark[nx][ny].first(SharkNumber의 next index)를 참고하여 빈칸이 있을 때와 없을 때 두번 상하좌우 순회를 하였습니다.

6. head array를 먼저 이동 시킴으로써 서로 만날 수 있는 경우를 고려하였습니다. head[nx][ny]에 먼저 와있던 Shark가 있다면, Shark의 번호를 고려하여 바뀔 수 있도록 하였고, M(상어의 개수)을 감소시켰습니다.

7. time에 따라 Fragment를 감소시켰습니다.

예제는 모두 맞았지만, 야속하게도 '틀렸습니다'만 반복이 됩니다. 혹시 문제를 푸셨거나 오류가 바로 보이신다면 첨언 부탁드립니다.

미리 감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <sstream>
#include <map>
#include <bitset>
#include <stack>
#include <cstring>

using namespace std;

#define INF 987654321
#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define formy(i, r, l) for (int i = r; i <= (int)l; ++i)
#define pii pair<int, int>
#define sz(a) int((a).size())
#define mp make_pair
#define LL long long
#define len(a) int((a).length())
#define pb push_back

#if 1

pii SHARK[20][20];
int head[20][20];
int dx[5]{0,-1,1,0,0};
int dy[5]{0,0,0,-1,1};
int chageDir[401][5][4];
int curDir[401];

int N,M,K;

bool rangeCheck(int nx,int ny){
    return (nx>=0 && nx<N && ny>=0 && ny<N);
}

int main(){
    cin>>N>>M>>K;
    forn(i,N) forn(j,N){
        cin >> SHARK[i][j].first;
        head[i][j]=SHARK[i][j].first;
        if(head[i][j]!=0) SHARK[i][j].second=K;
        else SHARK[i][j].second=0;
    }
    formy(i,1,M) cin>> curDir[i];
    formy(i,1,M){
        formy(j,1,4)
            forn(l,4){
                cin>>chageDir[i][j][l];
            }
    }

    int time=0;
    while(time <1000){
        time++;
        /* move with priority */
        queue<pii> q;
        forn(i,N) forn(j,N){
            if(head[i][j]!=0) q.push({i,j});
        }
        while(!q.empty()){
            int i=q.front().first;
            int j=q.front().second; q.pop();

            bool flag=true;  
            forn(l,4){
                int nx=i+dx[chageDir[head[i][j]][curDir[head[i][j]]][l]];
                int ny=j+dy[chageDir[head[i][j]][curDir[head[i][j]]][l]];

                if(rangeCheck(nx,ny) && SHARK[nx][ny].first==0){
                    flag=false;
                    if(head[nx][ny]==0) head[nx][ny]=head[i][j];
                    else if(head[nx][ny] > head[i][j]){
                        head[nx][ny]=head[i][j];
                        --M; if(M==1){printf("%d",time); return 0;}
                    }
                    else if(head[nx][ny] < head[i][j]){
                        --M;if(M==1){printf("%d",time); return 0;}
                    }
                    head[i][j]=0;
                    curDir[head[nx][ny]]=chageDir[head[nx][ny]][curDir[head[nx][ny]]][l];
                    break;
                }
            }
            /* 빈칸이 없을 때 */
            if(flag){
                forn(l,4){
                    int nx=i+dx[chageDir[head[i][j]][curDir[head[i][j]]][l]];
                    int ny=j+dy[chageDir[head[i][j]][curDir[head[i][j]]][l]];

                    if(rangeCheck(nx,ny) && SHARK[nx][ny].first==head[i][j]){
                        head[nx][ny]=head[i][j];
                        head[i][j]=0;
                        curDir[head[nx][ny]]=chageDir[head[nx][ny]][curDir[head[nx][ny]]][l];
                        break;
                    }
                }
            }
        }

        /* spend time */
        forn(i,N) forn(j,N)
            if(SHARK[i][j].second!=0) {
                SHARK[i][j].second--;
                if(SHARK[i][j].second==0) SHARK[i][j].first=0;
            }
        
        /* Final Plus Fragment */
        forn(i,N) forn(j,N){
            if(head[i][j]!=0) SHARK[i][j]={head[i][j],K};
        }
        
        if(M==1) break;
    }
    printf("%d",-1);
    return 0;
}

#endif

creativa 3년 전 2

해결했습니다.

99번줄의 에러가 있었네요.

head[nx][ny]가 변경되지 않을 경우에도 head[nx][ny]의 curDir를 변경하여 인접했을 경우에 에러가 발생했네요.

기쁘다.

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

문제

문제

출처

ICPC

19237문제 반례

creativa 3년 전 0

creativa 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말