글 읽기 - 어디서 틀렸는지 봐주실 수 있나요?

lcs11244 6년 전 0

어디서 잘못된지 잘 모르겠습니다.

S일때 검사를 시작해서 지금 현재 위치에 해당하는 번호를 체크해주고, 선택하지 않은 구역을 골라서 앞서 선택한 구역인지,

아니라면 기존에 한번이라도 선택한지 판별합니다.

그 후에 선택이 가능하다면 인접 4칸에 대해서 연결이 되어있는지를 확인합니다.

이렇게 연결이 되어있다면 다음으로 넘어갈때 S라면 더하고 아니라면 그냥 그 값을 던져주며 검사합니다.

디버깅할때는 생각대로 되는 것 같은데 어디서 틀린건지 모르겠어요#include <iostream>

#include <iostream>
#include <memory.h>
using namespace std;

char map[6][6];
bool check[1 << 25];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int ix, iy, nx, ny, dab;

bool find(int x, int y, int pick) //인접한 위치가 연결되어있는지 찾는다.
{
	for (int dir = 0; dir <4; dir++)
	{
		if (x + dx[dir] < 0 || y + dy[dir] < 0 || x + dx[dir] >= 5 || y + dy[dir] >= 5) continue;
		if (pick & (1 << ((y + dy[dir]) * 5 + (x + dx[dir]))))//연결 되어있다면 true
			return true;
	}
	return false;
}

void dfs(int d,int y, int S, int pick)
{
	check[pick] = true;
	if (d == 7) {
		if (S >= 4) dab++;
		return;
	}

	for (int i = y; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{	
			//검사 위치가 이미 선택되어 있거나 이미 같은 경우의 수라면 continue;
			if (check[(pick | (1 << (i * 5 + j)))]) continue; 
			if (find(j, i, pick)) // 선택되어 있지 않고, 같은 경우의 수가 아니라면 인접한지 검사
			{
				if(map[i][j] == 'S') dfs(d + 1, i, S + 1, pick | (1 << (i * 5 + j))); // 선택한 위치가 S라면 +1하고 다음 영역 아니라면 그냥 다음역역
				else
					dfs(d + 1, i, S, pick | (1 << (i * 5 + j)));
			}
		}
	}	
}

int main(void)
{
	for (int i = 0; i < 5; i++)
		cin >> map[i];

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			if (map[i][j] == 'S')
				dfs(1, i, 1, 1 << (i * 5 + j));

	cout << dab << endl;

	return 0;
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 봐주실 수 있나요?

lcs11244 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말