글 읽기 - 보물섬문제 시작점을 어떻게 잡아줘야할까요

lus6 7년 전 0

bfs로 풀려고했구요.

위에 표대로 나오게하면 되겠다 싶었는데 생각대로 안되는군요.

0,0부터 찾기 시작하니 저런식으로 검색하는데 어디서부터 잘못된걸까요.

계속 생각해봐도 안떠오르네요. 힌트라도 부탁드립니다.

#include <cstdio>
#include <queue>
#include <utility>

using namespace std;

int map[51][51];
int visited[51][51];

int n, m;
int ans = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };

void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ax = x + dx[i];
			int ay = y + dy[i];

			if (ax >= 0 && ax < n && ay >= 0 && ay < m && map[ax][ay] == 1 && visited[ax][ay] == 0)
			{
				visited[ax][ay] = map[x][y] + visited[x][y];
				q.push(make_pair(ax, ay));
				ans = max(ans, visited[ax][ay]);
			}
		}
	}
}
int main()
{
	char tmp;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) // 0은 바다, 1은 육지
	{
		getchar();
		for (int j = 0; j < m; j++)
		{
			scanf("%c", &tmp);
			if (tmp == 'W')
			{
				map[i][j] = 0;
			}
			else
			{
				map[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 1 && visited[i][j] == 0)
			{
				bfs(i, j);
			}
		}
	}

	printf("%d", ans);
	return 0;
}

h0ngjun7 7년 전 1

bfs를 수행하실 때마다 visited 배열을 초기화해주시면 되어요.

즉, 각 점을 시작점으로 지정하고 나머지 점들에 이르는 최단거리들 중 가장 큰 값을 매번 답을 담는 변수에 업데이트하면 됩니다.

h0ngjun7 7년 전 0

이 링크에 들어가보시면 제 코드가 있습니다. 참고하세용.

lus6 7년 전 0

아.. 그렇네요. 감사합니다.

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

문제

문제

출처

ICPC

보물섬문제 시작점을 어떻게 잡아줘야할까요

lus6 7년 전 0

h0ngjun7 7년 전 1

h0ngjun7 7년 전 0

lus6 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말