글 읽기 - 반례를 찾습니다

2cmosquare 1년 전 0

게시판에 있는 모든 반례 다 통과하는데 제출 하면 바로 틀렸다고 나오네요.

벽을 뚫고 온 경우와 그렇지 않은 경우를 구별해 큐에 넣어서 풀었습니다.

어디서 틀렸는지 모르겠어서 질문 올립니다.

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

using namespace std;

int map[1002][1002];
int visited[1002][1002][2]; //0: 벽을 뚫지 않고 왔을 때 현재 좌표까지 온 거리, 1: 벽을 뚫고 왔을 때 거리
queue<pair<pair<int, int>, bool>> que;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M, dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};

    memset(map, -1, sizeof(int)*1002*1002);
    memset(visited, -1, sizeof(int)*1002*1002*2); //아직 방문하지 않은 곳은 -1

    cin>>N>>M;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }

    visited[1][1][0]=1;

    que.push({{1, 1}, false});

    while(!que.empty())
    {
        int x=que.front().first.first;
        int y=que.front().first.second;
        bool through = que.front().second;
        que.pop();

        if(through) //벽을 뚫고 온 경우
        {
            for(int i=0; i<4; i++)
            {
                if(map[x+dx[i]][y+dy[i]]==0 && visited[x+dx[i]][y+dy[i]][1]==-1)
                {
                    que.push({{x+dx[i], y+dy[i]}, true});
                    visited[x+dx[i]][y+dy[i]][1]=visited[x][y][1]+1;
                }
            }
        }
        else //아직 벽을 뚫고 오지 않은 경우
        {
            for(int i=0; i<4; i++)
            {
                if(map[x+dx[i]][y+dy[i]]==0 && visited[x+dx[i]][y+dy[i]][0]==-1)
                {
                    que.push({{x+dx[i], y+dy[i]}, false});
                    visited[x+dx[i]][y+dy[i]][0]=visited[x][y][0]+1;
                }
                else if(map[x+dx[i]][y+dy[i]]==1 && visited[x+dx[i]][y+dy[i]][1]==-1)
                {
                    que.push({{x+dx[i], y+dy[i]}, true});
                    visited[x+dx[i]][y+dy[i]][1]=visited[x][y][0]+1;
                }
            }
        }
    }

    if((visited[N][M][0]==-1) != (visited[N][M][1]==-1))
    {
        cout<<max(visited[N][M][0], visited[N][M][1]);
    }
    else
    {
        cout<<min(visited[N][M][0], visited[N][M][1]);
    }

    return 0;
}

jyheo98 1년 전 0

5 5

00100

11000

00110

01011

00000

good:

bad:

-1

2cmosquare 1년 전 0

답변 감사드립니다. 하지만 제 코드로도 답이 9라고 정상적으로 출력되네요

jyheo98 1년 전 1

지금 보니 입력 부분을 고치니 맞는 코드네요.

for(int i=1; i<=N; i++)
{
string s; cin >> s;
for(int j=1; j<=M; j++)
{
map[i][j] = (s[j-1]=='1');
}
}

일케 문자열로 바꾸니 맞았어요.

2cmosquare 1년 전 1

오 고쳐주신대로 제출했더니 맞았어요!

근데 int로 받아서 바로 map에 넣는거랑 문자열로 받아서 int로 변환해서 map에 넣는게 무슨 차이가 있어서 맞고 틀린지는 모르겠네요ㅠ

두 방식 다 동일한 map을 만드는데 말이죠

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

문제

문제

출처

ICPC

반례를 찾습니다

2cmosquare 1년 전 0

jyheo98 1년 전 0

2cmosquare 1년 전 0

jyheo98 1년 전 1

2cmosquare 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말