글 읽기 - 질문에 있는 반례도 다 돌려 밨는데...틀린 곳을 못찾겠어요ㅠㅠ

yunyoung0309 4년 전 0

어느 부분이 틀렸는지 잘 모르겠습니다.ㅠㅠㅠ

#include <stdio.h>
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int N, M;
int map[1000][1000];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dis[1000][1000];
queue < pair<int, int>> q;
int a_cnt;
int days;
void bfs();
int main()
{
	cin >> M >> N;
	int r_cnt = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 0 || map[i][j] == 1 )
			{
				a_cnt++;
			}
		}
	} 

	fill(&dis[0][0], &dis[999][999], -1);
	
	bfs();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 1)
			{
				r_cnt++;              // 다 채워졌나
			}
		}
	}

	if (r_cnt == a_cnt)
	{
		cout << days << endl;
	}
	else
	{
		cout << "-1" << endl;
	}
}

void bfs()
{
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 1)      // 사과가 있는 부부을 queue에 넣음
			{
				pair<int, int> p;
				p.first = i;
				p.second = j;
				dis[i][j] = 0;
				q.push(p);
			}
		}
	}

	

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

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			pair<int, int> np;
			np.first = nx;
			np.second = ny;

			if (nx >= 0 && ny >= 0 && nx < N && ny < M && dis[nx][ny] == -1)
			{
				if (map[nx][ny] == 0 )
				{
					map[nx][ny] = 1;
					dis[nx][ny] = dis[x][y] + 1;
					q.push(np);
			
				}

				else if (map[nx][ny] == 1)
				{
					q.push(np);
					dis[nx][ny] = 0;
				}

				else // map[][]==-1
				{
					dis[nx][ny] = 0;
				}

			}
		}

		
		days = dis[q.front().first][q.front().second];
		q.pop();

	}
	

}

yehyun 4년 전 0

아래 입력에 대해 제가 AC 받은 코드는 -1을, 질문자님이 올리신 코드는 0을 출력합니다.

다만, 이것이 적절한 반례인지는 잘 모르겠습니다.

개인적으로는 이 입력에 대해 어떤 출력을 해야 하는지가 문제에 명시되어 있는 편이 좋을 것 같습니다.

input
2 2
-1 -1
-1 -1

13579wkd 2년 전 0

@yehyun

"토마토가 하나 이상 있는 경우만 입력으로 주어진다." 는 조건으로 위 반례는 문제조건에 해당되지 않을 것 같습니다

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

문제

문제

출처

ICPC

질문에 있는 반례도 다 돌려 밨는데...틀린 곳을 못찾겠어요ㅠㅠ

yunyoung0309 4년 전 0

yehyun 4년 전 0

13579wkd 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말