글 읽기 - 반례 다 맞았는데 왜 틀린지는 모르겠습니다.

opcy02 3년 전 0

3차원 배열을 사용하기 귀찮아 2차원 배열을 사용하여 풀어보았습니다.

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

int M, N, K, S;
typedef pair<int, int> NODE;
vector<vector<int>> adj;

NODE moves[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

bool AllTomato()
{
	for (int i = 1; i <= N * S; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (adj[i][j] == 0) {
				return false;
			}
		}
	}
	return true;
}

bool AllTomato2()
{
	for (int i = 1; i <= N * S; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (adj[i][j] != -1) {
				return false;
			}
		}
	}
	return true;
}

int BFS()
{
	queue<NODE> q;
	queue<NODE> temQ;
	int cnt = 0;

	if (AllTomato2()) return -1;

	// 첫 토마토의 상태가 들어있는 위치를 찾는
	for (int i = 1; i <= N * S; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (adj[i][j] == 1) temQ.push(NODE(i, j));
		}
	}

	while (temQ.size())
	{
		if (AllTomato()) break;
		q = temQ;

		queue<NODE> clear;
		temQ.swap(clear);

		while (q.size())
		{
			NODE here = q.front(); q.pop();
			int y = here.first;
			int x = here.second;

			for (int i = 0; i < 4; i++)
			{
				int ny = y + moves[i].first;
				int nx = x + moves[i].second;

				int dy = y + N;
				int uy = y - N;

				if (uy >= 1 && adj[uy][x] == 0)
				{
					adj[uy][x] = 1;
					temQ.push(NODE(uy, x));
				}

				if (dy <= N * S && adj[dy][x] == 0)
				{
					adj[dy][x] = 1;
					temQ.push(NODE(dy, x));
				}

				if (adj[ny][nx] != -1 && adj[ny][nx] == 0) {
					adj[ny][nx] = 1;
					temQ.push(NODE(ny, nx));
				} 
			}
		}

		cnt++;

		if (temQ.size() == 0) 
			if (!AllTomato()) { cnt = -1; }
	}

	return cnt;
}

int main()
{
	scanf("%d %d %d", &M, &N, &S);
	adj.resize(N * S+ 2, vector<int>(M + 2, -1));

	for (int i = 1; i <= N * S; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%d", &K);
			adj[i][j] = K;
		}
	}

	printf("%d", BFS());
}

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

문제

문제

출처

ICPC

반례 다 맞았는데 왜 틀린지는 모르겠습니다.

opcy02 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말