글 읽기 - 도움 부탁드립니다..

millennier 8년 전 0

풀이 방식은 Combination을 이용하여 모든 경우를 검색하였고 문제의 조건에 따라 가능회수를 증가하였습니다.

모두 S의 입력부터 여러 테스트를 정답 소스와 비교해보았는데 틀린답이 없었지만 제출하면 0%도 검사를 안하고 틀립니다가 나옵니다.

전체 경우를 다 검사하기때문에 틀릴수 가 없다고 생각하는데 왜 틀린걸까요?

#include <iostream>
#include <queue>
#include <stdio.h>

#define N (25)
#define R (7)

using namespace std;

typedef struct Info
{
	char name;
	int posID;
}Info;

typedef struct Pos
{
	int y;
	int x;
}Pos;

Info Map[N];
Pos PosLT[N];
Pos curPos, prevPos;

int solution;
int bufArr[N];

void initPosLT()
{
	for (int h = 0; h < 5; h++)
	{
		for (int w = 0; w < 5; w++)
		{
			PosLT[h * 5 + w].x = w + 1;
			PosLT[h * 5 + w].y = h + 1;
		}
	}
}

bool isConnected(int arr[])
{
	bool isVisited[6][6];
	int map[6][6];
	int dr[4] = { 0, 0 , 1, -1 };
	int dc[4] = { 1, -1, 0, 0 };

	for (int h = 0; h < 6; h++)
	{
		for (int w = 0; w < 6; w++)
		{
			isVisited[h][w] = false;
			map[h][w] = 0;
		}
	}

	for (int i = 0; i < R; i++)
	{
		Pos curPos = PosLT[arr[i] - 1];
		map[curPos.y][curPos.x] = 1;
	}

	int count = 0;
	queue<Pos> Q;
	Pos pos = PosLT[arr[0] - 1];
	Q.push(pos);
	isVisited[pos.y][pos.x] = true;
	count++;

	while (!Q.empty())
	{
		pos = Q.front();
		Q.pop();

		if (pos.x < 1 || pos.y < 1 || pos.x > 5 || pos.y > 5)
			continue;

		for (int i = 0; i < 4; i++)
		{
			Pos nextPos;
			nextPos.y = pos.y + dr[i];
			nextPos.x = pos.x + dc[i];

			if (!isVisited[nextPos.y][nextPos.x] && map[nextPos.y][nextPos.x])
			{
				Q.push(nextPos);
				isVisited[nextPos.y][nextPos.x] = true;
				count++;
			}
		}
	}

	return count == R ? true : false;
}

void combinationUtil(Info arr[], int data[], int start, int end, int index, int r)
{
	if (index == r)
	{
		int countOfS = 0;

		for (int i = 0; i < r; i++)
		{
			if (Map[data[i] - 1].name == 'S')
				countOfS++;
		}

		if (countOfS >= 4 && isConnected(data))
			solution++;
	}

	for (int i = start; i <= end && end - i + 1 >= r - index; i++)
	{
		data[index] = arr[i].posID;
		combinationUtil(arr, data, i + 1, end, index + 1, r);
	}
}

void printCombination(Info arr[], int n, int r)
{
	initPosLT();
	solution = 0;

	for (int i = 0; i < N; i++)
		bufArr[i] = 0;

	combinationUtil(arr, bufArr, 0, n - 1, 0, r);
}

int main()
{
	char c[5][5];
	int countOfMap = 1;
	for (int i = 0; i < 5; i++) 
	{
		scanf("%s", &c[i]);
		for (int j = 0; j < 5; j++)
		{
			Map[i * 5 + j].name = c[i][j];
			Map[i * 5 + j].posID = countOfMap++;
		}
	}

	printCombination(Map, N, R);
	printf("%d\n", solution);
	return 0;
}

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

문제

문제

출처

ICPC

도움 부탁드립니다..

millennier 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말