글 읽기 - 어디서틀린건지모르겠어요!

wjavm2 4년 전 0

게시판에 반례도 다 맞고, 정답도 다 나오는데 자꾸 틀렸습니다가 나와요! 빠트린부분이 어느부분일까요?ㅠㅠ

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

struct info { int x, y; };
int N, M;
int Count;
int Map[110][110];
int cpy[110][110];
int visit[110][110];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<info>Q;


bool finish(); //남은치즈가 있는지 검사
void paint_background(); //공기(배경)부분을 Map = -1로바꿔주는 함수
void find_outlinecheese(); //공기와 맞닿은치즈 찾는함수

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> Map[i][j];
		}
	}

	memcpy(&cpy, &Map, sizeof(Map)); //Map배열 cpy에복사

	Q.push({ 0, 0 });//처음 배경과 치즈안의 공기층 구분해주기위해서 (0,0)부터 BFS돌림
	cpy[0][0] = -1; //배경(공기)=-1로 바꿔줌
	
	while (1) {

		paint_background();
		if (finish())break; //만약 치즈가 소멸했다면 while문 break;
		Count++;//몇번 돌아야 치즈가 없어지는지
		find_outlinecheese();
	}

	int result1 = Count;
	int result2 = 0;

	for(int i = 0; i<N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (visit[i][j] == Count-1 && Map[i][j]==1) //원래 맵에서 치즈이고, 방문시간이 Count-1이면 카운트
				result2++;
		}
	}

	cout << result1 << endl;
	cout << result2 << endl;

	return 0;
}


void paint_background()
{
	while (!Q.empty())
	{
		int cx = Q.front().x;
		int cy = Q.front().y;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
			if (cpy[nx][ny] == 0) //테두리치즈의 다음위치가 공기면
			{
				cpy[nx][ny] = -1; 
				Q.push({ nx,ny });
			}
		}
	}
}

void find_outlinecheese()
{
	while (!Q.empty())
	{
		Q.pop(); //queue초기화
	}

	for (int i = 1; i < N-1; i++)
	{
		for(int j = 1; j<M-1; j++)
		{
			if (cpy[i][j] == 1 && visit[i][j]==-1) //방문하지않았고, 치즈인것중
			{
				if (cpy[i - 1][j] == -1 || cpy[i][j - 1] == -1 || cpy[i + 1][j] == -1 || cpy[i][j + 1] == -1) //만약 위,아래,왼,오른쪽이 배경이면
				{
					Q.push({ i,j }); //배경과맞닿은 치즈의테두리이므로 queue에 넣어줌
					cpy[i][j] = 0;
					visit[i][j] = Count-1; 
				}
			}
		}
	}
}

bool finish()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (cpy[i][j] == 1)return false; //맵에 치즈가있으면 false리턴
		}
	}
	return true;
}

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

문제

문제

출처

ICPC

어디서틀린건지모르겠어요!

wjavm2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말