글 읽기 - 아기상어 테스트케이스와 질문게시판 반례 통과하지만 2%넘기지못합니당 ㅠㅠ

wkdrnjs913 1년 전 0

혹시 로직문제인지... 다른 반례가있는지 알수있을까요 ..?

#include <iostream>
#include <queue>
#include <vector>
#include "memory.h"

using namespace std;

int n;
int map[22][22];
bool bmap[22][22];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
pair<int,int> playerpos;
vector<pair<int,pair<int,int> > > find_fish_pos;
int player_level = 2;
int player_exp = 0;
int result = 0;

void clear()
{
    for (int i = 1; i <= n ; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            bmap[i][j] = 0;
        }
    }
}
// 주변 가까운 물고기 탐색
void find_fish(pair<int,int> pos)
{
    bool find = false;
    int minimum = 0;
    //memset(bmap,0,sizeof(bmap));
    clear();
    find_fish_pos.clear();
    priority_queue<pair<int,pair<int,int> > , vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int > > > > pq;
    pq.push(make_pair(0,make_pair(pos.first,pos.second)));
    while(!pq.empty())
    {
        int time = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        if (find == true && minimum <= time)
            continue ;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >=1 && yy >= 1 && xx <= n && yy <= n)
            {
                if (!bmap[yy][xx] && map[yy][xx] <= player_level)
                {
                    bmap[yy][xx] = true;
                    if (map[yy][xx] < player_level && map[yy][xx] > 0)
                    {
                        minimum = time + 1;
                        find = true;
                        find_fish_pos.push_back(make_pair(time+ 1,make_pair(xx,yy)));
                    }
                    else
                        pq.push(make_pair(time + 1, make_pair(xx,yy)));
                }
            }
        }
    }
    
}
void go()
{
    int x = find_fish_pos[0].second.first;
    int y = find_fish_pos[0].second.second;
    int t = find_fish_pos[0].first;
    for (int i = 1; i < find_fish_pos.size(); i++)       // 찾은 물고기가 많다면 가장 위 / 가장 왼쪽 물고기 선택
    {
        if (t < find_fish_pos[i].first)
            break;
        if (y > find_fish_pos[i].second.second)
        {
            x = find_fish_pos[i].second.first;
            y = find_fish_pos[i].second.second;
        }
        if (y == find_fish_pos[i].second.second)
        {
            if (x >= find_fish_pos[i].first)
            {
                x = find_fish_pos[i].second.first;
                y = find_fish_pos[i].second.second;
            }
        }
    }
    player_exp++;
    if (player_exp == player_level)                 // 레벨업 처리
    {
        player_exp = 0;
        player_level++;
    }
    // 이동
    map[y][x] = 0;
    playerpos.first = x;
    playerpos.second = y;
    result += t;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 9)
            {
                playerpos = make_pair(j,i);
                map[i][j] = 0;
            }   
        }
    }
    while (1)
    {
        find_fish(playerpos);
        if (!find_fish_pos.empty())
        {
            go();
        }
        else
            break;
    }
    cout << result << "\n";
    return 0;
}

jyheo98 1년 전 1

반례입니다.

4
1 0 1 0
6 0 5 0
1 0 0 0
9 0 2 2

good:
12

bad:
13

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

문제

문제

출처

ICPC

아기상어 테스트케이스와 질문게시판 반례 통과하지만 2%넘기지못합니당 ㅠㅠ

wkdrnjs913 1년 전 0

jyheo98 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말