글 읽기 - 질문 게시글의 모든 반례를 통과했으나 틀리다고 합니다. ㅜㅜ

qotmd01 2년 전 0

bfs로 각 상어의 위치에서 갈 수 있는 모든 물고기의 위치를 찾고 정렬하는 방식으로 했습니다.

문제의 테스트케이스와 질문글의 반례 20개 정도 테스트 해봤는데 3프로에서 틀렸다고 합니다. ㅜ

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

int time_count = 0;
int eat_count = 0;
int max_eat = 2;

typedef struct{
    int i;
    int j;
    int cost;
    int distance;
} fish;


bool Comparedistance(const fish& x, const fish& y){
    return x.distance < y.distance ;
}
fish made_info(int i, int j, int cost){
    fish temp;
    temp.i = i;
    temp.j = j;
    temp.cost = cost;
    
    return temp;
}

std::vector<std::vector<int>> matrix(20,std::vector<int>(20,0));

void bfs_shark(fish baby_shark, int n){
    // 모든 방문점 초기화, 거리 배열 생성
    std::vector<std::vector<int>> visit(n,std::vector<int>(n,0));
    std::vector<std::vector<int>> distance(n,std::vector<int>(n,0));
    std::vector<fish> can_it;

    
    // 큐 생성
    std::queue<fish> q;
    q.push(baby_shark);
    visit[baby_shark.i][baby_shark.j] = 1;
    distance[baby_shark.i][baby_shark.j] = 0;
    matrix[baby_shark.i][baby_shark.j] = 0;
    
    while ( ! q.empty()) {
        fish current = q.front();
        q.pop();
        
        int x = current.i;
        int y = current.j;
        
        // 먹을 수 있다면 push
        if (matrix[x][y] != 0 && (current.cost < baby_shark.cost)) {
            current.distance = distance[current.i][current.j];
            can_it.push_back(current);
        }
        
        if (x + 1 < n && visit[x+1][y] != 1 && matrix[x+1][y] <= baby_shark.cost) {
            q.push(made_info(x+1, y, matrix[x+1][y]));
            distance[x+1][y] = distance[x][y] + 1;
            visit[x+1][y] = 1;
        }
        
        if (x - 1 >= 0 && visit[x-1][y] != 1 && matrix[x-1][y] <= baby_shark.cost) {
            q.push(made_info(x-1,y,matrix[x-1][y]));
            distance[x-1][y] = distance[x][y] + 1;
            visit[x-1][y] = 1;
        }
        
        if (y + 1 < n && visit[x][y+1] != 1 && matrix[x][y+1] <= baby_shark.cost) {
            q.push(made_info(x,y+1,matrix[x][y+1]));
            distance[x][y+1] = distance[x][y] + 1;
            visit[x][y+1] = 1;
        }
        
        if (y - 1 >= 0 && visit[x][y-1] != 1 && matrix[x][y-1] <= baby_shark.cost) {
            q.push(made_info(x,y-1,matrix[x][y-1]));
            distance[x][y-1] = distance[x][y] + 1;
            visit[x][y-1] = 1;
        }
        
    }
    
    if (can_it.size() == 0) {
        return;
    }
    else{
        sort(can_it.begin(),can_it.end(),Comparedistance);
        
        fish temp = can_it[0];
        fish temp_min_i = can_it[0]; // 가장 위에 있는
        fish temp_min_j = can_it[0]; // 가장 아래에 있는

        
        for (int i = 0; i < 4; i++) {
            if (can_it[i].i < temp_min_i.i && can_it[i].distance == temp.distance) {
                temp_min_i = can_it[i];
            }
            
            if (can_it[i].j < temp_min_j.j && can_it[i].distance == temp.distance) {
                temp_min_j = can_it[i];
            }

        }
        
        if (temp_min_i.i == temp_min_j.i) {
            temp = temp_min_j;
        }
        else{
            temp = temp_min_i;
        }
        
        time_count += temp.distance;
        baby_shark.i = temp.i;
        baby_shark.j = temp.j;
        eat_count += 1;
        if (eat_count == max_eat) {
            eat_count = 0;
            baby_shark.cost += 1;
            max_eat = baby_shark.cost;
        }
        
        bfs_shark(baby_shark, n);
        
    }
    
}


int main(void){
    fish baby_shark;
    int N;
    std::cin >> N;
    //matrix.resize(N * N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            std::cin >> matrix[i][j];
            if (matrix[i][j] == 9) {
                baby_shark.i = i;
                baby_shark.j = j;
                baby_shark.cost = 2;
                baby_shark.distance = 0;
            }
        }
    }
    
    bfs_shark(baby_shark, N);
    
    std::cout << time_count << std::endl;
    
    
    
    return 0;
    
}

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

문제

문제

출처

ICPC

질문 게시글의 모든 반례를 통과했으나 틀리다고 합니다. ㅜㅜ

qotmd01 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말