글 읽기 - 시간 초과가 발생합니다.

ainch96 7년 전 0

25% 정도에서 시간초과가 발생합니다.

벡트래킹으로 작성했습니다.

저는 이것 이상으로 짧게 짜는 방법이 떠올리지 않는데,

변수 선언 같은 기술적인 방법으로 시간을 줄이는 가벼운 여러 요령 등이나

혹은 소스 전반적으로 시간을 오래 걸릴 것 같은 잘못된 부분을 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <queue>
using namespace std;

typedef double db; 
void move(char t,char a[][5]){
	char b[4][5];
	queue < char > q;
	for(int i=0;i<4;++i)
		for(int j=0;j<4;++j)
			b[i][j] = 'E';
	if(t=='L'){
		for(int i=0;i<4;++i){
			for(int j=0;j<4;++j){
				if(a[i][j]!='E')
					q.push(a[i][j]);
			}
			int p=0;
			while(!q.empty()){
				b[i][p++] = q.front();
				q.pop();
			}
		}
	}
	else if(t=='R'){
		for(int i=0;i<4;++i){
			for(int j=3;j>=0;--j){
				if(a[i][j]!='E')
					q.push(a[i][j]);
			}
			int p=3;
			while(!q.empty()){
				b[i][p--] = q.front();
				q.pop();
			}
		}
	}
	else if(t=='T'){
		for(int j=0;j<4;++j){
			for(int i=0;i<4;++i){
				if(a[i][j]!='E')
					q.push(a[i][j]);
			}
			int p=0;
			while(!q.empty()){
				b[p++][j] = q.front();
				q.pop();
			}
		}
	}
	else if(t=='B'){
		for(int j=0;j<4;++j){
			for(int i=3;i>=0;--i){
				if(a[i][j]!='E')
					q.push(a[i][j]);
			}
			int p=3;
			while(!q.empty()){
				b[p--][j] = q.front();
				q.pop();
			}
		}
	}
	for(int i=0;i<4;++i)
		for(int j=0;j<4;++j)
			a[i][j] = b[i][j];
}
int mid(char a[][5]){
	int ret=0;
	for(int i=1;i<=2;++i)
		for(int j=1;j<=2;++j)
			if(a[i][j]!='E')++ret;
	return ret;
}
int tot(char a[][5]){
	int ret=0;
	for(int i=0;i<=3;++i)
		for(int j=0;j<=3;++j)
			if(a[i][j]!='E')++ret;
	return ret;
}
char a[4][5];
char obj[4][5];
vector < char > v;
db go(db p,int d,int n){
	if(n==d){
		for(int i=0;i<4;++i)
			for(int j=0;j<4;++j)
				if(a[i][j]!=obj[i][j])return 0;
		return p;
	}
	else{
		db ret = 0;
		if(v[d]=='W' || v[d]=='G'){
			int ma = mid(a);
			int ta = tot(a);
			if(ma<=3){
					if(ma==0){
						for(int i=1;i<=2;++i)
							for(int j=1;j<=2;++j){
								a[i][j] = v[d];
								ret += go(p/4,d+1,n);
								a[i][j] = 'E';
							}
					}
					else if(ma==1){
						for(int i=1;i<=2;++i){
							for(int j=1;j<=2;++j){
								if(a[i][j]!='E'){
									a[i%2==0?1:2][j%2==0?1:2]=v[d];
									ret += go(p,d+1,n);
									a[i%2==0?1:2][j%2==0?1:2]='E';
								}
							}
						}
					}
					else if(ma==2){
						for(int i=1;i<=2;++i)
							for(int j=1;j<=2;++j){
								if(a[i][j]=='E'){
									a[i][j] = v[d];
									ret += go(p/2,d+1,n);
									a[i][j] = 'E';
								}
							}
					}
					else if(ma==3){
						for(int i=1;i<=2;++i)
							for(int j=1;j<=2;++j)
								if(a[i][j]=='E'){
									a[i][j] = v[d];
									ret += go(p,d+1,n);
									a[i][j] = 'E';
								}
					}
			}
			else{
				int td = 12 - (ta - 4);
				for(int i=0;i<4;++i)
					for(int j=0;j<4;++j){
						if(a[i][j]!='E')continue;
						ret += go(p/td,d+1,n);
					}
			}
		}
		else{
			char t[4][5];
			for(int i=0;i<4;++i)
				for(int j=0;j<4;++j)
					t[i][j]=a[i][j];
			move(v[d],a);
			ret = go(p,d+1,n);
			for(int i=0;i<4;++i)
				for(int j=0;j<4;++j)
					a[i][j]=t[i][j];
		}
		return ret;
	}
}
int main(){
	int t;
	for(scanf("%d",&t);t--;){
		int n;scanf("%d",&n);
		char t[2];
		v.clear();
		for(int i=0;i<n;++i){
			scanf("%s",t);
			v.push_back(t[0]);
		}
		for(int i=0;i<4;++i){
			scanf("%s",obj[i]);
			for(int j=0;j<4;++j)
				a[i][j] = 'E';
		}
		printf("%.10lf\n",go((double)1,0,n));
	}
}

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

문제

문제

출처

ICPC

시간 초과가 발생합니다.

ainch96 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말