글 읽기 - 반례 찾아주시면 감사드리겠습니다!

tompark58981 1년 전 0

예제도 다 맞고 질문에 있는 반례들도 다 제대로 나오는데 제출하자마자 틀렸다고 나오네요...

우선순위 큐로 벽을 적게 뚫는 곳을 먼저 방문한다는 로직으로 풀었습니다.

감사합니다!

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

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool visited[101][101];
int grid[101][101];
int N,M;

int main(){

    cin >> M >> N;

    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        for(int j=M-1;j>=0;j--){
            grid[i][j] = num%10;
            num/=10;
        }
    }

    q.push({0,{0,0}});
    visited[0][0] = true;

    while(!q.empty()){
        int num = q.top().first;
        int cx = q.top().second.first;
        int cy = q.top().second.second;
        q.pop();

        if(cx==M-1&&cy==N-1){
            cout << num << '\n';
            return 0;
        }

        for(int i=0;i<4;i++){
            int nx = cx+dir[i][0];
            int ny = cy+dir[i][1];

            if(nx<0||ny<0||nx>=M||ny>=N||visited[ny][nx]) continue;

            visited[ny][nx] = true;
            if(grid[ny][nx])
                q.push({num+1,{nx,ny}});
            else
                q.push({num,{nx,ny}});
        }
    }

    return 0;
}

tompark58981 1년 전 0

100자리까지 되는 수를 int로 입력 받으려해서 틀렸네요...ㅎㅎ

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

문제

문제

출처

ICPC

반례 찾아주시면 감사드리겠습니다!

tompark58981 1년 전 0

tompark58981 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말