글 읽기 - 토마토 반례가 혹시 있을까요?

2015112119 5년 전 0

2178 미로 탐색이랑 비슷한 게 있는 것 같아서 코드를 재활용했습니다.

일단 1과 -1의 개수를 구해 토마토가 모두 익은 경우를 구분했습니다.

그리고 처음에 토마토가 1일 때 큐에 집어넣은 다음 bfs를 구현했습니다.

큐의 처음부터 시작해 인수의 근처에 0이 있을경우 거기로 이동하는 식으로 구현했습니다.

그리고 visited에는 지금까지 이동한 횟수를 저장시켰구요.

예제의 답은 모두 정답처리지만 틀렸다고 나오네요. 제가 놓치거나 한 부분이 있을까요?

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

#define inside(x,y) ((x >= 0) && (y >= 0) && (x < n) && (y < m))

int arr[1001][1001], n, m, Minus = 0, Plus = 0;
int visited[1001][1001], cnt=999999;

queue<pair<int,int>>qu;

int bfs(int x, int y) {
	
	visited[x][y] = 1;

	while (!qu.empty()) {
		x = qu.front().first;
		y = qu.front().second;

		qu.pop();

		if (inside(x + 1, y) && arr[x + 1][y] == 0 && visited[x + 1][y] == -1) {
			visited[x + 1][y] = visited[x][y] + 1;
			arr[x + 1][y] = 1;
			qu.push(pair<int, int>(x + 1, y));
		}if (inside(x, y + 1) && arr[x][y + 1] == 0 && visited[x][y + 1] == -1) {
			visited[x][y + 1] = visited[x][y] + 1;
			arr[x][y + 1] = 1;
			qu.push(pair<int, int>(x, y + 1));
		}if (inside(x - 1, y) && arr[x - 1][y] == 0 && visited[x - 1][y] == -1) {
			visited[x - 1][y] = visited[x][y] + 1;
			arr[x - 1][y] = 1;
			qu.push(pair<int, int>(x - 1, y));
		}if (inside(x, y - 1) && arr[x][y - 1] == 0 && visited[x][y - 1] == -1) {
			visited[x][y - 1] = visited[x][y] + 1;
			arr[x][y -1] = 1;
			qu.push(pair<int, int>(x, y - 1));
		}
	}

	return visited[x][y];
}

int main() {

	memset(visited, -1, sizeof(visited));

	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1) Minus++;
			if (arr[i][j] == 1) { Plus++; qu.push({ i,j }); }
		}
	}

	if ((n*m - Minus) == Plus) cout << 0;
	else {
		int xpos = qu.front().first;
		int ypos = qu.front().second;

		
		try {
			int ans = bfs(xpos, ypos);
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (arr[i][j] == 0) throw - 1;
				}
			}
			cout << ans - 1;
		}
		catch (int excep) {
			cout << excep;
		}
	}

}

luniro 5년 전 1

출력:
-1

정답:
1

2015112119 5년 전 0

감사합니다! 덕분에 해결했어요~

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

문제

문제

출처

ICPC

토마토 반례가 혹시 있을까요?

2015112119 5년 전 0

luniro 5년 전 1

2015112119 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말