글 읽기 - 조건 하나만 추가하면 될 것 같습니다만..ㅜㅜ

minhye11 4년 전 0

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

이런 경우에 잘 안됩니다ㅜㅜ 조건을 어떻게 추가해야할지 모르겠어요

도와주세요ㅠㅠㅠ

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int tomato[1000][1000];
int is_searched[1000][1000];
queue <int> x;
queue <int> y;
vector <int> other;
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
int M, N;
int maximum = 0;

void bfs(int i, int j){
    is_searched[i][j] = 1;
    
    x.push(i);
    y.push(j);
    
    while(! x.empty()){
        for(int a = 0; a < 4; a++){
            int ni = x.front() + di[a];
            int nj = y.front() + dj[a];
            if(ni < 0 || ni >= N || nj < 0 || nj >=M){
                continue;
            }
            if(tomato[ni][nj] == -1){
                continue;
            }
            if(is_searched[ni][nj] == 0){
                is_searched[ni][nj] = is_searched[x.front()][y.front()] + 1;
                if(is_searched[ni][nj] > maximum){
                    maximum = is_searched[ni][nj];
                }
                x.push(ni);
                y.push(nj);
            }
            
        }
        x.pop();
        y.pop();
    }
}


int main()
{
    cin >> M >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> tomato[i][j];
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(tomato[i][j] == 1 && is_searched[i][j] == 0){
                bfs(i, j);
            }
        }/*일단 숙성이 완료되었을 때의 날짜 구하기*/
    }
    cout << maximum << "\n";
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cout << is_searched[i][j];
        }
        cout << "\n";
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(is_searched[i][j] == 0 && tomato[i][j] != -1){
                cout << -1;
                return 0;
            }
        }
    }/*토마토가 모두 익지 못하는 상황*/
    
    cout << 1;
    
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(tomato[i][j] == 1 || tomato[i][j] == -1){
                count += 1;
            }
        }
    }
    if(count == N * M){
        cout << 0;
        return 0;
    }/* 토마토가 첨부터 다 익음*/
    
    cout << 2;
    
    if(maximum == 0){
        cout << 0;
    }else{
        cout << maximum - 1;
    }
    
    cout << 3;
    return 0;/*토마토가 모두 익었을 때, 날짜를 구하기*/
}

nahwasa 4년 전 1

https://www.ideone.com/KNol8X

일단 테스트용 코드는 빼고올려주셔야 이해가 될듯싶습니다 ㅠ

seico75 4년 전 3

올리신 반례와 같이 1이 여러개인 경우, 익은 토마토가 매턴 주위 토마토를 익게하니까 중간에서 만나야 합니다.

그런데 올리신 소스는 좌상단 토마토만 일을 하지 우하단 토마토는 일을 할 여지가 없습니다.

매턴 양쪽 토마토에게 기회를 균등하기 주려면...

bfs에서 처음 큐에 모든 1(익은 토마토)를 넣고 시작을 하면 될 것 같습니다.

minhye11 4년 전 0

감사합니다!!!

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

문제

문제

출처

ICPC

조건 하나만 추가하면 될 것 같습니다만..ㅜㅜ

minhye11 4년 전 0

nahwasa 4년 전 1

seico75 4년 전 3

minhye11 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말