글 읽기 - 100%에서 틀리는데 반례좀 찾아주세요..

kyujeong 6년 전 0

DFS로 돌면서 육지와 붙어있는 바다를 한 칸씩 채워나가고 전 단계에서 채웠던 땅만 다시 DFS로 돌면서 붙어있는 바다 채우고

이런 식으로 반복되는 알고리즘입니다.

테스트케이스 잘 나오고 제가 여러개 만들어서 테스트해봐도 다 맞게 나오는데 100%에서 계속 틀려서 답답하네요..

반례좀 찾아주시면 감사하겠습니다ㅠㅠ

#include <iostream>
using namespace std;

int map[101][101];
int N;
bool check[101][101];
int moveX[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int moveY[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int curIslandNum = 1;
int curMoveCount = 1;
int moveCount[101][101];
bool findAnswer;
int shortestLength;

void firstDFS(int y, int x)
{
	if (findAnswer)
		return;
	check[y][x] = true;

	for (int i = 0; i < 4; i++)
	{
		int nY = y + moveY[i];
		int nX = x + moveX[i];

		if (nY < 0 || nX < 0 || nY >= N || nX >= N)
			continue;
		else {
			if (map[nY][nX] == 0)
			{
				map[nY][nX] = curIslandNum;
				moveCount[nY][nX] = curMoveCount;
			}
			else if (map[nY][nX] != 1 && map[nY][nX] != curIslandNum)
				findAnswer = true;
			else if (!check[nY][nX] && map[nY][nX] == 1)
				firstDFS(nY, nX);
		}
	}
}

void DFS(int y, int x)
{
	if (findAnswer)
		return;
	check[y][x] = true;

	for (int i = 0; i < 4; i++)
	{
		int nY = y + moveY[i];
		int nX = x + moveX[i];

		if (nY < 0 || nX < 0 || nY >= N || nX >= N || map[nY][nX] == 1)
			continue;
		else
		{
			if (map[nY][nX] == 0)
			{
				map[nY][nX] = curIslandNum;
				moveCount[nY][nX] = curMoveCount;
			}
			else if (map[nY][nX] != curIslandNum)
			{
				if (moveCount[nY][nX] == curMoveCount)
					shortestLength = curMoveCount;
				else
					shortestLength = curMoveCount - 1;
				findAnswer = true;
			}
			else if (!check[nY][nX] && moveCount[nY][nX] < curMoveCount && map[nY][nX] == curIslandNum)
				DFS(nY, nX);
		}
	}

	for (int i = 4; i < 8; i++)
	{
		int nY = y + moveY[i];
		int nX = x + moveX[i];

		if (!check[nY][nX] && moveCount[nY][nX] < curMoveCount && map[nY][nX] == curIslandNum)
			DFS(nY, nX);
	}
}

int main()
{
	std::ios::sync_with_stdio(false);

	cin >> N;

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


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j] == 1 && !check[i][j])
			{
				curIslandNum++;
				firstDFS(i, j);
			}
		}
	}

	if (findAnswer)
	{
		cout << "1";
		return 0;
	}
	
	while (1)
	{
		curMoveCount += 2;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (moveCount[i][j] == curMoveCount - 2 && !check[i][j])
				{
					curIslandNum = map[i][j];
					DFS(i, j);
				}
				if (findAnswer)
				{
					cout << shortestLength;
					return 0;
				}
			}
		}
	}

	return 0;
}

djm03178 6년 전 1

반례입니다.

1 0 0 0 0

0 0 0 0 0

0 0 1 0 0

0 0 0 0 1

2가 출력되어야 하지만, 3이 출력됩니다.

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

문제

문제

출처

ICPC

100%에서 틀리는데 반례좀 찾아주세요..

kyujeong 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말