글 읽기 - 체점도중 틀리는데 반례를 못찾겠어요 .. ㅠㅠ

hun222y 7년 전 0

해당 문제에서 가장자리는 입력이 치즈가 없다고 하여서

2 2

1 1

1 0 이러한 예제는 고려를 하지 않았습니다. (가장자리가 차있는경우 무한루프 돌게됨)

공기가 2면이상 닿지 않은경우 큐에 넣고 반복횟수를 카운트 했는데 체점 도중 틀리는데 반례를 찾기가 힘드네요 .. ㅠㅠ

치즈가 공기에 닿는 부분을 잘못처리해준것일까요??

#include<iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

int m,n,arr[111][111],cnt,arr2[111][111],ans;
bool visit[111][111];
queue<pair<int,pair<int,int>>> q;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

bool chk(int y , int x){
    return 0<y && y<=n && 0<x && x<=m;
}

int main(){
    scanf("%d%d" , &n,&m);
    cnt = 0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d" , &arr[i][j]);
            if(arr[i][j] == 1){
                arr2[i][j] = arr[i][j];
                cnt++;
                q.push({0,{i,j}});
            }else{
                arr2[i][j] = 0;
            }
        }
    }
    while(!q.empty()){
        int a=0;
        int y = q.front().second.first;
        int x = q.front().second.second;
        int cc = q.front().first;
        
        if(ans!= cc){               //복사
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    arr[i][j] = arr2[i][j];
                }
            }
            ans = cc;
        }
        q.pop();
        for(int i=0;i<4;i++){
            int yy = y+dy[i];
            int xx = x+dx[i];
            if(chk(yy,xx) && arr[yy][xx] == 0){
                a++;
            }
            if(a<2 && i ==3){//공기에 안닿은 경우
                q.push({cc+1,{y,x}});
                arr2[y][x] = 1;
            }
            if(i == 3 && a>=2){//닿은경우
                arr2[y][x] = 0;
            }
        } 
    }
    if(ans == 0 && cnt == 0){
        printf("0\n");
        return 0;
    }
    if(ans == 0 && cnt!= 0){
        printf("1\n");
        return 0;
    }
    printf("%d\n" , ans+1);

    return 0;
}

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

문제

문제

출처

ICPC

체점도중 틀리는데 반례를 못찾겠어요 .. ㅠㅠ

hun222y 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말