글 읽기 - 반례 딱 하나만 찾아주세요

khqwer 3년 전 0

백준에서 진짜 한번에 통과하는 경우는 ㅠ.ㅠ 없네요...

계시판 반례를 아래서 부터 전부 넣어본거 같은데 맞다고 나오는데

답은 틀렸다네요...

고수님들 반례 딱 하나만 찾아주시면 안될까요.

이게 무지 이상한게

ios::sync_with_stdio(0);
cin.tie(0);

를 지우면 14%에서는 통과가 되고 또 21%에서 막혀버립니다.. ㅠㅠ 뭐가 문제일가요.

.............인풋을 스트링으로 받지 않았다고 틀렸다고 나온거네요.........

inputs를 string으로 바꾸고

inputs%2==1을 inputs[i]=='1'하니까 통과되네요...뭔거 이상하다....

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;
using visiting=tuple<int,int,int,bool>;


int main()
{
    int N,M,inputs;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    vector<vector<bool>> board(N,vector<bool>(M, false)),visited1(N,vector<bool>(M, false)),visited2(N,vector<bool>(M, false));
    queue<visiting>histroy;
    histroy.push({0,0,1,true});
    for(auto&u:board){
        cin>>inputs;
        for (int i = 0; i <M ; ++i) {
            if(inputs%2==1)u[M-1-i].flip();
            inputs/=10;
        }
    }
    int dx[]{1,-1,0,0},dy[]{0,0,1,-1};
    auto beforeBreakingWall{[&](visiting& A){
        for (int i = 0; i <4 ; ++i) {
            pair<int,int> tt{get<0>(A)+dx[i],get<1>(A)+dy[i]};
            if(tt.first<0||tt.first>=N||tt.second<0||tt.second>=M)continue;
            if(board[tt.first][tt.second]&&!visited1[tt.first][tt.second]){
                visited2[tt.first][tt.second]=true;
                histroy.push({tt.first,tt.second,get<2>(A)+1,false});
            } else if (!board[tt.first][tt.second]&&!visited1[tt.first][tt.second]){
                visited1[tt.first][tt.second]=true;
                histroy.push({tt.first,tt.second,get<2>(A)+1,true});
            }
        }
    }};
    auto afterBrokenWall{[&](visiting& A){
        for (int i = 0; i <4 ; ++i) {
            pair<int,int> tt{get<0>(A)+dx[i],get<1>(A)+dy[i]};
            if(tt.first<0||tt.first>=N||tt.second<0||tt.second>=M)continue;
            if(board[tt.first][tt.second])continue;
            if(visited2[tt.first][tt.second])continue;
            visited2[tt.first][tt.second]=true;
            histroy.push({tt.first,tt.second,get<2>(A)+1,false});
        }
    }};
    while(!histroy.empty()){
        auto presentp{histroy.front()};
        if(get<0>(presentp)==N-1&&get<1>(presentp)==M-1)break;
        histroy.pop();
        if(get<3>(presentp)){
            beforeBreakingWall(presentp);
        } else afterBrokenWall(presentp);
    }
    if(get<0>(histroy.front())==N-1&&get<1>(histroy.front())==M-1)cout<<get<2>(histroy.front());
    else cout<<-1;
}

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

문제

문제

출처

ICPC

반례 딱 하나만 찾아주세요

khqwer 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말