글 읽기 - 2206 왜 틀렸습니다가 나오는지 모르겠습니다 ㅠ

heesung4767 4년 전 0

계속 100퍼센트에서 틀렸습니다가 나오는데 그 이유를 모르겠습니다.

이유나 반례를 올려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>

using namespace std;

int n,m;
int map[1001][1001] = {0, };
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int memo[1001][1001][2] = {0, };
queue<pair<pair<int,int>,pair<int,int>>> q;

bool isPossible(int a, int b){
    if(a>=1 && a<=n && b>=1 && b<=m){
      return true;
    }
    return false;
}

void bfs(){
    int dx, dy, a, b, check, cnt;
    
    while(!q.empty()){
        a = q.front().first.first;
        b = q.front().first.second;
        check = q.front().second.first;
        cnt = q.front().second.second;
        q.pop();
        
        for(int i=0;i<4;i++){
            dy = a + dir[i][0];
            dx = b + dir[i][1];
            if(isPossible(dy, dx)){
                if(map[dy][dx]){
                    if(check && !memo[dy][dx][check-1]){
                        pair<int,int> sp(dy, dx);
                        pair<int,int> cc(check-1, cnt+1);
                        pair<pair<int,int>,pair<int,int>> tmp(sp,cc);
                        memo[dy][dx][check-1] = cnt+1;
                        q.push(tmp); 
                    }
                }
                else if(!memo[dy][dx][check]){
                    pair<int,int> sp(dy, dx);
                    pair<int,int> cc(check, cnt+1);
                    pair<pair<int,int>,pair<int,int>> tmp(sp,cc);
                    memo[dy][dx][check] = cnt+1;
                    q.push(tmp);                 
                }
            }
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n>>m;
    char str[2000];
    for(int i=1;i<=n;i++){
        cin>>str;
        for(int j=1;j<=m;j++){
            map[i][j] = str[j-1] - 48;
        }
    }
    
    pair<int,int> sp(1,1);
    pair<int,int> cc(1,1);
    pair<pair<int,int>,pair<int,int>> tmp(sp,cc);
    q.push(tmp);
    
    bfs();
    
    if(!memo[n][m][0] && !memo[n][m][1]){
        cout<<"-1";
    }
    else if(!memo[n][m][0]){
            cout<<memo[n][m][1];
    }
    else if(!memo[n][m][1]){
            cout<<memo[n][m][0];
    }
    else{
        cout<<min(memo[n][m][0], memo[n][m][1]);
    }
    return 0;
}

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

문제

문제

출처

ICPC

2206 왜 틀렸습니다가 나오는지 모르겠습니다 ㅠ

heesung4767 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말