글 읽기 - 왜 안되는지 잘 모르겠어서 질문드립니다(BFS)

nestle7474 2년 전 0

자꾸 10%에서 틀립니다 문제 예시는 다 돌아가고, 게시판에 있는 반례도 찾아보며 돌렸는데 문제가 없어서요 어디에 문제가 있는지 알려주실 수 있을까요?

#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

int n, m, waterCnt;
char board[51][51];
int distWater[51][51];
int distBeaver[51][51];
int caveX, caveY;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> waterQ;
queue<pair<int, int>> beaverQ;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			distWater[i][j] = -1;
			distBeaver[i][j] = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char c;
			cin >> c;
			board[i][j] = c;

			if (c == '*')
			{
				waterQ.push({ i,j });
				distWater[i][j] = 0;
			}
			if (c == 'S')
			{
				beaverQ.push({ i,j });
				distBeaver[i][j] = 0;
			}
			if (c == 'D')
			{
				caveX = i;
				caveY = j;
			}
		}
	}

	while (!waterQ.empty())
	{
		auto cur = waterQ.front();
		waterQ.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			else
			{
				if (board[nx][ny] != 'X' && distWater[nx][ny] == -1 && board[nx][ny] != 'D' && board[nx][ny] != '*')
				{
					distWater[nx][ny] = distWater[cur.x][cur.y] + 1;
					waterQ.push({ nx, ny });
				}
			}
		}
	}

	while (!beaverQ.empty())
	{
		auto cur = beaverQ.front();
		beaverQ.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			else
			{
				if (board[nx][ny] == 'D')
				{
					distBeaver[nx][ny] = distBeaver[cur.x][cur.y] + 1;
					cout << distBeaver[nx][ny];
					return 0;
				}
				if (board[nx][ny] != 'X' && distBeaver[nx][ny] == -1 && distBeaver[cur.x][cur.y] + 1 < distWater[nx][ny])
				{
					distBeaver[nx][ny] = distBeaver[cur.x][cur.y] + 1;
					beaverQ.push({ nx, ny });
				}
			}

		}
	}

	cout << "KAKTUS";

}

nestle7474 2년 전 0

물에 대한 BFS를 돌때 안채워지는 상황이 생길 수 있어서 108번째줄 조건문을 만족을 못하는 경우가 생깁니다

그래서 visit 배열을 새로 생성해주어 물의 방문 여부를 체크하고, 추가로 조건문을 달아주어 해결하였습니다

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

문제

문제

출처

ICPC

왜 안되는지 잘 모르겠어서 질문드립니다(BFS)

nestle7474 2년 전 0

nestle7474 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말