글 읽기 - 토마토의 반례를 알고싶습니다...

ehdwns1249 5년 전 0

"틀렸습니다"입니다!

제 무능한 머리는 반례를 찾지 못하네요...

일단 BFS라는 느낌으로다가 짜봤는데 어디가 잘못 된 걸까요?

날씨도 추운데 재능기부좀 해주십셔!!!!

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	queue<int> q1;
	queue<int> q2;
	queue<int> q3;

	int **arr;
	int **visit;
	int count = 0;
	int N, M;

	cin >> M >> N; // M과 N 순서바꿈!

	arr = new int*[N];
	visit = new int*[N];

	for (int i = 0; i < N; i++) {
		arr[i] = new int[M];
		visit[i] = new int[M];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j]; //2차원에 배열에 삽입
			if (arr[i][j] == 0) { //0 개수 카운트
				count++;
			}
			else if (arr[i][j] == 1){ //익은 토마토가 있는 경우 큐에 삽입, q3은 깊이
				q1.push(i); q2.push(j); q3.push(0);
			}
		}
	}
	if (q1.empty()) { //익은 토마토가 없는 경우
		cout << "-1\n";

		for (int i = 0; i < N; i++) {
			delete[] arr[i];
			delete[] visit[i];
		}
		delete[] arr;
		delete[] visit;

		return 0;
	}

	int a = q1.front(); q1.pop();
	int b = q2.front(); q2.pop();
	int level = q3.front(); q3.pop();

	while (1) {
		if (a - 1 >= 0) {//위에칸확인
			if (arr[a - 1][b] == 0 && visit[a - 1][b] < 1) {//아직 방문하지 않았으면서 안익은경우 방문 표시, 큐에 인덱스+레벨(깊이) 삽입, 안익은 토마토개수 --
				visit[a - 1][b] = 1;
				q1.push(a - 1); q2.push(b); q3.push(level + 1);
				count--;
			}
		}
		if (b - 1 >= 0) {//왼쪽칸확인
			if (arr[a][b - 1] == 0 && visit[a][b - 1] < 1) {//아직 방문하지 않았으면서 안익은경우 방문 표시, 큐에 인덱스+레벨(깊이) 삽입, 안익은 토마토개수 --
				visit[a][b - 1] = 1;
				q1.push(a); q2.push(b-1); q3.push(level + 1);
				count--;
			}
		}
		if (a + 1 < N) {//아래칸확인
			if (arr[a + 1][b] == 0 && visit[a + 1][b] < 1) {//아직 방문하지 않았으면서 안익은경우 방문 표시, 큐에 인덱스+레벨(깊이) 삽입, 안익은 토마토개수 --
				visit[a + 1][b] = 1;
				q1.push(a + 1); q2.push(b); q3.push(level + 1);
				count--;
			}
		}
		if (b + 1 < M) {//오른쪽칸확인
			if (arr[a][b + 1] == 0 && visit[a][b + 1] < 1) {//아직 방문하지 않았으면서 안익은경우 방문 표시, 큐에 인덱스+레벨(깊이) 삽입, 안익은 토마토개수 --
				visit[a][b+1] = 1;
				q1.push(a); q2.push(b+1); q3.push(level + 1);
				count--;
			}
		}

		if (q1.empty()) {//큐가 비어있으면 반복문 종료
			break;
		}
		else {//큐가 비어있지 않으면 큐에서 값을 가져오고 pop!
			a = q1.front(); q1.pop();
			b = q2.front(); q2.pop();
			level = q3.front(); q3.pop();
		}
	}

	if (count != 0) {//안익은 토마토가 1개라도 있다면
		cout << "-1\n";
	}
	else {//다익었다면 깊이 출력, 처음부터 모두 익어있던 경우도 여기포함
		cout << level << "\n";
	}
	for (int i = 0; i < N; i++) {
		delete[] arr[i];
		delete[] visit[i];
	}
	delete[] arr;
	delete[] visit;
}

xcm1321 5년 전 1

예제 1번이 8이 나왔다가 -1이 나왔다가 하네요.

ehdwns1249 5년 전 0

입력부분 제외하고 반복문으로 예제1번을 1000번을 돌려봤을 때 모두 8이
나오는데... -1이 나오질 않습니다...

djm03178 5년 전 1

visit이 초기화되지 않았습니다.

ehdwns1249 5년 전 0

감사합니다!

visit 제가 확인했을땐 음수 쓰레기값 밖에 없길래 굳이 초기화안했었는데
아닌 경우도 있나보네요!
visit 초기화 하니까 통과했습니다
존경합니다

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

문제

문제

출처

ICPC

토마토의 반례를 알고싶습니다...

ehdwns1249 5년 전 0

xcm1321 5년 전 1

ehdwns1249 5년 전 0

djm03178 5년 전 1

ehdwns1249 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말