글 읽기 - 왜 시간초과가 나는지 모르겠습니다.

kwondoil 7년 전 0

나름대로 최대한 가지치기를 하여서 시간을 줄일만큼 줄였는데 계속 시간 초과가 나네요 고수님들의 도움 부탁드립니다.

#include<stdio.h>
#define MAX 1000
#define MAX_ 100000
#define LD 0
#define RD 1
#define LU 2
#define RU 3
int N, M;
char map[MAX][MAX];
int visited[MAX][MAX];
int Bcnt;
int BArr_x[MAX_];
int BArr_y[MAX_];
int Wcnt;
int WArr_x[MAX_];
int WArr_y[MAX_];
int sol;

int check(int idx,int type)
{
	int ret = 0;
	switch (type)
	{
		case LD:
			if (map[BArr_x[idx]][BArr_y[idx]] == 'B'&&map[BArr_x[idx]][BArr_y[idx] - 1] == 'W'&&map[BArr_x[idx] + 1][BArr_y[idx]] == 'W'
				&&visited[BArr_x[idx]][BArr_y[idx]] == 0&&visited[BArr_x[idx]][BArr_y[idx] - 1] == 0 &&visited[BArr_x[idx] + 1][BArr_y[idx]] == 0)
			{
				visited[BArr_x[idx]][BArr_y[idx]] = 1;//me
				visited[BArr_x[idx]][BArr_y[idx] - 1] = 1;//left
				visited[BArr_x[idx] + 1][BArr_y[idx]] = 1;//down
				ret = 1;
			}
			break;
		case RD:
			if (map[BArr_x[idx]][BArr_y[idx]] == 'B'&&map[BArr_x[idx]][BArr_y[idx] + 1] == 'W'&&map[BArr_x[idx] + 1][BArr_y[idx]] == 'W'
				&&visited[BArr_x[idx]][BArr_y[idx]] == 0 && visited[BArr_x[idx]][BArr_y[idx] + 1] == 0 && visited[BArr_x[idx] + 1][BArr_y[idx]] == 0)
			{
				visited[BArr_x[idx]][BArr_y[idx]] = 1;//me
				visited[BArr_x[idx]][BArr_y[idx] + 1] = 1;//right
				visited[BArr_x[idx] + 1][BArr_y[idx]] = 1;//down
				ret = 1;
			}
			break;
		case LU:
			if (map[BArr_x[idx]][BArr_y[idx]] == 'B'&&map[BArr_x[idx]][BArr_y[idx] - 1] == 'W'&&map[BArr_x[idx] - 1][BArr_y[idx]] == 'W'
				&&visited[BArr_x[idx]][BArr_y[idx]] == 0 && visited[BArr_x[idx]][BArr_y[idx] - 1] == 0 && visited[BArr_x[idx] - 1][BArr_y[idx]] == 0)
			{
				visited[BArr_x[idx]][BArr_y[idx]] = 1;//me
				visited[BArr_x[idx]][BArr_y[idx] - 1] = 1;//left
				visited[BArr_x[idx] - 1][BArr_y[idx]] = 1;//up
				ret = 1;
			}
			break;
		case RU:
			if (map[BArr_x[idx]][BArr_y[idx]] == 'B'&&map[BArr_x[idx]][BArr_y[idx] + 1] == 'W'&&map[BArr_x[idx] - 1][BArr_y[idx]] == 'W'
				&&visited[BArr_x[idx]][BArr_y[idx]] == 0 && visited[BArr_x[idx]][BArr_y[idx] + 1] == 0 && visited[BArr_x[idx] - 1][BArr_y[idx]] == 0)
			{
				visited[BArr_x[idx]][BArr_y[idx]] = 1;//me
				visited[BArr_x[idx]][BArr_y[idx] + 1] = 1;//right
				visited[BArr_x[idx] - 1][BArr_y[idx]] = 1;//up
				ret = 1;
			}
			break;
	}
	return ret;
}
void uncheck(int idx, int type)
{
	switch (type)
	{
		case LD:
			visited[BArr_x[idx]][BArr_y[idx]] = 0;//me
			visited[BArr_x[idx]][BArr_y[idx] - 1] = 0;//left
			visited[BArr_x[idx] + 1][BArr_y[idx]] = 0;//down
			break;
		case RD:
			visited[BArr_x[idx]][BArr_y[idx]] = 0;//me
			visited[BArr_x[idx]][BArr_y[idx] + 1] = 0;//right
			visited[BArr_x[idx] + 1][BArr_y[idx]] = 0;//down
			break;
		case LU:
			visited[BArr_x[idx]][BArr_y[idx]] = 0;//me
			visited[BArr_x[idx]][BArr_y[idx] - 1] = 0;//left
			visited[BArr_x[idx] - 1][BArr_y[idx]] = 0;//up
			break;
		case RU:
			visited[BArr_x[idx]][BArr_y[idx]] = 0;//me
			visited[BArr_x[idx]][BArr_y[idx] + 1] = 0;//right
			visited[BArr_x[idx] - 1][BArr_y[idx]] = 0;//up
			break;
	}
}
int isAllWhiteVisited()
{
	for (int i = 0; i < Wcnt; i++)
	{
		if (!visited[WArr_x[i]][WArr_y[i]])
			return 0;
	}
	return 1;
}

void logic(int step)
{
	if (sol == 1)
		return;
	if (step == Bcnt)
	{
		if (isAllWhiteVisited())
		{
			sol = 1;
		}
		return;
	}
	for (int type = 0; type < 4; type++)
	{
		int tmp = check(step, type);
		if (tmp == 1)
		{
			logic(step + 1);
			uncheck(step, type);
		}
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	for (int tc = 0; tc < T; tc++)
	{
		scanf("%d %d", &N, &M);
		sol = Bcnt = Wcnt = 0;

		char tmp[MAX];
		for (int i = 1; i <= N; i++)
		{
			scanf("%s", &tmp);
			for (int j = 1; j <= M; j++)
			{
				map[i][j] = tmp[j - 1];
				visited[i][j] = 0;
				if (map[i][j] == 'B')
				{
					BArr_x[Bcnt] = i;
					BArr_y[Bcnt++] = j;
				}
				if (map[i][j] == 'W')
				{
					WArr_x[Wcnt] = i;
					WArr_y[Wcnt++] = j;
				}
			}
		}
		logic(0);
		if (sol)
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}

	}
	return 0;
}

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

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다.

kwondoil 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말