글 읽기 - 토마토-BFS 문제 질문입니다(테스트케이스는 모두통과)

gmldus0407 4년 전 0

테스트케이스는 모두 통과했는데 왜 틀렸다고 나올까요 ㅠㅠ도와주세요 ㅜㅜ

#include <iostream>
#include <cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int mm = 0;
int M,N;
int found = 0;
queue <pair <int, int> > q;
bool visited[1000][1000];
int A[1000][1000];
int map[1000][1000];  
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

void bfs() {

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		visited[x][y] = true;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (0 <= dx && dx < N && 0 <= dy && dy < M) {
				if (map[dx][dy] == 0 && visited[dx][dy] == false) {
					visited[dx][dy] = true;
					map[dx][dy] = 1;
					A[dx][dy] = A[x][y] + 1;
					q.push(make_pair(dx, dy));
				}
			}
		}
	}

}
int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> M;   
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				q.push(make_pair(i, j));
				A[i][j] = 0;
			}//익은 토마토가 있는 자리위치를 큐에 넣음.
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				found = 1;
			}
		}
	}
	if (found == 0) cout << "0" << "\n"; //이미 다 익은 상태이면
	bfs();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				found = 2;
			}
		}
	}
	if (found == 2) cout << "-1" << "\n";
	else {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				mm = max(mm, A[i][j]);
			}
		}
		cout << mm << "\n";
	}

}

gmldus0407 4년 전 0

아 제가 방금 해결하긴했는데

혹시 익은 토마토가 아닌 토마토들의 A배열 값은 설정을 안해줘서 나중에 문제가 생기는건가요?? 문제가될지 잘 몰랐네요 ㅠㅠ

qahira 4년 전 0

C/cpp에서 전역변수로 선언하고 초기화를 안한다면 기본적으로 0으로 초기화 됩니다. 토마토 가 있는곳을 0으로 놓으셧는데, 그렇다면 없는곳 잇는곳 구별이 안되서 잘 안풀렸던것 같습니다.

푸셨다니 축하 드립니다 ㅎㅎ

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

문제

문제

출처

ICPC

토마토-BFS 문제 질문입니다(테스트케이스는 모두통과)

gmldus0407 4년 전 0

gmldus0407 4년 전 0

qahira 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말