글 읽기 - 반례 좀 찾아주시면 안될까요?ㅜㅜ

sennom3 3년 전 1

예시 입력이랑 질문 게시판 모든 반례 통과 했는데 78프로에서 틀리네요.

뭐가 문제인지 찾아주실 수 있을까요?

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

typedef struct Pos {
    int row;
    int col;
} Pos;
typedef struct DistPos {
    int distance;
    Pos pos;
} DistPos;
typedef struct SharkInfo {
    Pos pos;
    int size; 
} SharkInfo;

int N;
vector<vector<int> > map;
vector<vector<bool> > visited;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
SharkInfo info; 

void getInput() {
    cin >> N;
    map.assign(N+2, vector<int>(N+2, -1));
    visited.assign(N+2, vector<bool>(N+2, false));

    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 9) {
                info = {{i, j}, 2};
            }
        }
    }
}
void initVisited() {
    visited.assign(N+2, vector<bool>(N+2, false));
}

DistPos selectFish() {
    DistPos ret = {4*N, {4*N, 4*N}};
    queue<DistPos> q;
    q.push({0, info.pos});
    visited[info.pos.row][info.pos.col] = true;
    while(!q.empty()) {
        DistPos here = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            Pos next = {here.pos.row + dr[i], here.pos.col + dc[i]};
            if(map[next.row][next.col] != -1 && !visited[next.row][next.col] && map[next.row][next.col] <= info.size && here.distance+1 <= ret.distance) {
                if(map[next.row][next.col] && map[next.row][next.col] < info.size) {
                    if(next.row < ret.pos.row) {
                        ret = {here.distance+1, next};
                    } else if(next.row == ret.pos.row) {
                        if(next.col < ret.pos.col) {
                            ret = {here.distance+1, next};
                        }
                    }
                }
                else {
                    q.push({here.distance + 1, next});
                    visited[next.row][next.col] = true;
                }
            }
        }
    }

    return ret;
}

void solution() {
    int fishNum = 0;
    int totalTime = 0;
    DistPos eatenFish;
    while (true) {
        eatenFish = selectFish();
        if(eatenFish.distance == 4*N) {
            break;
        }
        initVisited();

        map[info.pos.row][info.pos.col] = 0;
        info.pos = eatenFish.pos;
        map[info.pos.row][info.pos.col] = 9;

        totalTime += eatenFish.distance;
        fishNum += 1;
        if(fishNum == info.size) {
            info.size += 1;
            fishNum = 0;
        }
    }

    cout << totalTime;
}

int main() {
    getInput();
    solution();
    return 0;
}

jabbong 3년 전 6

반례입니다.

20
0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 3 4 4
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 3 3 4 4
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4
    
답 : 913
질문자님의 코드의 답 : 0

sennom3 3년 전 1

감사합니다ㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

반례 좀 찾아주시면 안될까요?ㅜㅜ

sennom3 3년 전 1

jabbong 3년 전 6

sennom3 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말