글 읽기 - 게시판에 반례를 넣어봐도 맞게 나와요 도와주세요(코드설명있음!)

miz722 3년 전 0

반례를 찾아주시거나 어디가 틀렸는지 알려주시면 정말 감사하겠습니다

#include <iostream>
#include <queue>
using namespace std;
int m,n;
int graph[1001][1001];
bool visit[1001][1001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
queue<pair<int,int>> q;

void dfs(int x, int y){
    if(x<0||y<0||x>=n||y>=m)    return;//판을 넘어가면 그만
    if(graph[x][y]!=1||visit[x][y])  return;//0이거나 -1이거나 이미 방문했으면 그만
    //위에서 걸러짐 : 1이고 방문하지 않은것
    visit[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0||ny<0||nx>=n||ny>=m)    continue;
        if(graph[nx][ny]==0) {
            //1이고 인접한것이 0일때 인접한것을 큐에 넣는다
            q.push(make_pair(nx, ny));
        }
    }
}
int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j <m; j++)
            cin >> graph[i][j];

    for(int i = 0; i < n; i ++){
        for(int j = 0; j <m; j++){
            if(graph[i][j]==1&&!visit[i][j]){
                dfs(i,j);
            }
        }
    }//첫번째날 익어야하는것을 q에 넣는다
    int index = q.size();
    int answer = 0;
    while(!q.empty()) {//q가 empty가 아닐때
        while (index) {//하루당 담겨있는 q만큼 반복
            pair<int, int> curr = q.front();
            q.pop();
            graph[curr.first][curr.second]=1;
            dfs(curr.first,curr.second);
            index--;
        }
        index = q.size();//새로 담긴 큐의 사이즈(다음날 익어야하는것들)
        answer++;//하루끝
    }
    int check = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j <m; j++){
            if(graph[i][j]==0){
                cout << -1;
                return 0;
            }
            else if(graph[i][j]==-1){
                check++;
            }
        }
    }
    if(check== n*m){
        cout << -1;
        return 0;
    }
    cout << answer;
    return 0;

}

kms9937 3년 전 0

반례입니다.

11 11
0 0 0 0 1 0 -1 -1 0 0 0 
0 -1 1 1 0 0 1 1 0 0 0 
0 0 0 0 -1 1 0 0 1 0 0 
0 0 -1 0 0 -1 -1 0 0 0 -1 
1 1 -1 0 0 1 0 0 0 -1 1 
-1 0 0 0 0 0 1 0 0 1 0 
0 1 0 -1 0 0 0 0 1 1 1 
0 0 0 1 0 0 0 0 0 -1 0 
0 0 0 0 0 0 0 0 0 0 -1 
-1 0 0 0 0 0 1 1 0 0 1 
-1 0 0 0 0 -1 -1 0 0 0 -1 

정답:4
오답:5

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

문제

문제

출처

ICPC

게시판에 반례를 넣어봐도 맞게 나와요 도와주세요(코드설명있음!)

miz722 3년 전 0

kms9937 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말