글 읽기 - 반례 좀 찾아주세요ㅠㅠㅠㅠ

fincrusia 3년 전 0

깔끔하게 짰다고 좋아하고 있었고 테스트케이스도 다 맞았는데 도대체 왜 틀렸는지 모르겠습니다.

priority_queue로 탐색했습니다.

#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;

int N;
int map[20][20];
bool checked[20][20];
int row;
int col;
int size = 2;
int eat = 0;


struct comp{
    bool operator()(pair<pair<int,int>,int> A, pair<pair<int,int>,int> B){
        if(abs(A.first.first - row) + abs(A.first.second - col) != abs(B.first.first - row) + abs(B.first.second - col))
            return abs(A.first.first - row) + abs(A.first.second - col) > abs(B.first.first - row) + abs(B.first.second - col);
        if(A.first.first != B.first.first) return A.first.first > B.first.first;
        else return A.first.second > B.first.second;
    }
};



int main(){
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            scanf("%d",&(map[i][j]));
            if(map[i][j] == 9){
                map[i][j] = 0;
                row = i;
                col = j;
            }
        }
    }

    int counter = 0;

    for(;;){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                checked[i][j] = false;
            }
        }


        bool done = false;
        priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int>>,comp> q;
        checked[row][col] = true;
        q.push(pair<pair<int,int>,int>(pair<int,int>(row,col),0));


        for(;q.size();){

            pair<pair<int,int>,int> temp = q.top();
            q.pop();
            int currow = temp.first.first;
            int curcol = temp.first.second;
            int local_count = temp.second;

            if(map[currow][curcol] > 0 && map[currow][curcol] < size){

                map[currow][curcol] = 0;
                done = true;
                eat++;
                if(eat == size){
                    size++;
                    eat = 0;
                }
                counter += local_count;
                row = currow;
                col = curcol;
                break;
            }


            if(currow > 0 && checked[currow-1][curcol] == false && map[currow - 1][curcol] <= size){
                checked[currow-1][curcol] = true;
                q.push(pair<pair<int,int>,int>(pair<int,int>(currow-1,curcol),local_count + 1));
            }
            if(curcol > 0 && checked[currow][curcol-1] == false && map[currow][curcol - 1] <= size){
                checked[currow][curcol-1] = true;
                q.push(pair<pair<int,int>,int>(pair<int,int>(currow,curcol-1),local_count + 1));
            }
            if(curcol < N - 1 && checked[currow][curcol+1] == false && map[currow][curcol + 1] <= size){
                checked[currow][curcol+1] = true;
                q.push(pair<pair<int,int>,int>(pair<int,int>(currow,curcol+1),local_count + 1));
            }
            if(currow < N - 1 && checked[currow+1][curcol] == false && map[currow + 1][curcol] <= size){
                checked[currow+1][curcol] = true;
                q.push(pair<pair<int,int>,int>(pair<int,int>(currow+1,curcol),local_count + 1));
            }

        }

        if(done) continue;
        else break;

    }

    printf("%d\n",counter);

}

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

문제

문제

출처

ICPC

반례 좀 찾아주세요ㅠㅠㅠㅠ

fincrusia 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말