글 읽기 - 왜 틀렸는지 모르겠습니다

rlagksrlf12 4년 전 0

어디선가 문제가 있었던 것 같은데 잘모르겠네요... 질문게시판에있는 예제들은 다 돌려봤습니다!!

#include<stdio.h>
#include"algorithm"
using namespace std;
typedef pair<int, int> point2D;
int tomato[1003][1003];
int visited[1003][1003];
point2D queue[1000001];
int front = 0, rear = 0;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
void push(int y, int x)
{
	queue[rear].first = y;
	queue[rear++].second = x;
}
point2D pop()
{
	point2D Node;
	Node.first = queue[front].first;
	Node.second = queue[front++].second;
	return Node;
}
void bfs(int y, int x, int n, int m)
{
	visited[y][x] = 1;
	push(y, x);
	while (front != rear)
	{
		point2D Node = pop();
		for (int i = 0; i < 4; i++)
		{
			if (tomato[Node.first + dy[i]][Node.second + dx[i]] == 0 && (visited[Node.first + dy[i]][Node.second + dx[i]] > visited[Node.first][Node.second]|| visited[Node.first + dy[i]][Node.second + dx[i]] == 0) && Node.first + dy[i] < n&&Node.first + dy[i] >= 0 && Node.second + dx[i] < m&&Node.second + dx[i] >= 0)
			{
				visited[Node.first + dy[i]][Node.second + dx[i]] = visited[Node.first][Node.second] + 1;
				push(Node.first + dy[i], Node.second + dx[i]);
			}
		}
	}
}
int check(int n, int m)
{
	int flag = 1;
	for (int i = 0; i < n; i++) // 모두 익어 있는 경우 체크 하나라도 안익으면 안 됨
	{
		for (int j = 0; j < m; j++)
		{
			if (tomato[i][j] == 0) flag = 0;
		}
	}
	if (flag == 1) return 0;
	flag = 0;
	for (int i = 0; i < n; i++)// 하나라도 익을 수 없는 경우 모두 익어야함
	{
		for (int j = 0; j < m; j++)
		{
			if (tomato[i][j] == 0&&visited[i][j]==0) flag = 1;
		}
	}
	if (flag == 1) return -1;
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			max = max < visited[i][j] ? visited[i][j] : max;
		}
	}
	return max-1;
}
int main()
{
	int n, m,answer;
	scanf("%d %d", &m, &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &tomato[i][j]);
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (tomato[i][j] == 1)
			{
				bfs(i, j, n, m);
			}
		}
	}
	answer=check(n, m);
	printf("%d\n", answer);
	return 0;
}

wjdgud0621 4년 전 1

Bfs 시작칸에 visited해줘야해요

rlagksrlf12 4년 전 0

visited도 해봤는데 안되네요 ㅠㅠ 코드 수정해서 다시 바꿔놨습니다

plm2034 4년 전 0

큐를 늘리던지 front와 rear가 최댓값을 넘으면 0으로 돌아오도록 해야할것 같습니다.

1 0 0 0 1

-1 -1 -1 -1 -1

위 경우에 좌상단에서 bfs 했을때 visit가

1 2 3 4 ㅁ

ㅁ ㅁ ㅁ ㅁ ㅁ

그후 우상단에서

ㅁ ㅁ ㅁ 2 1

ㅁ ㅁ ㅁ ㅁ ㅁ

이런식으로 2번 중복방문하는 토마토가 있으면
푸쉬도 2중으로 되므로 큐 1000*1000개로는 부족할 수 있습니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다

rlagksrlf12 4년 전 0

wjdgud0621 4년 전 1

rlagksrlf12 4년 전 0

plm2034 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말