글 읽기 - 왜 틀렸는지 모르겠습니다.

soloplay 2년 전 0

벽면과 맨 윗면의 상태를 비트마스킹으로 표현해서 DFS를 돌렸습니다. 그 값을 해싱해서 맵으로 대응시켜 겹치는 경우의 수를 뺴주었는데 어느 부분에서 틀렸는지 모르겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long llu;
llu n,k,c[6]={2,3,0,1,5,4},d[20][20],cnt,r[6]={4,0,1,5,2,3},o;
map<llu,int> s;
void DFS(int dep) {
	if(dep==-1) {
		if(n==(1llu<<16)-1) {
			llu t[4]={0,0,0,0},a[4]={0,0,0,0},b=0;
			for(int q=0;q<4;q++) { 
				for(int p=q;p<16;p+=4) {
					t[q]+=(1llu<<((b++)*2))*((k>>(p*2))&3);
					//cout<<((k>>(p*2))&3); 
			}
			//cout<<" ";
			b=0;
       		}
    		for(int p=0;p<4;p++) {
				for(int q=0;q<4;q++) {
					a[p]+=((1llu<<(((p+q)&3)*8))*t[q]);
				}
				a[p]+=((1llu<<33)*o);
				if(s[a[p]]) 
				{
					//cout<<"*\n";
					return;
				}
       			s[a[p]]=1;
			}	
			cnt++;
			//cout<<"\n";
		}
		return;
	}
	for(int i=0;i<6;i++) {
		for(int j=0;j<6;j++) {
			if(i==j||i==c[j]) continue;
			llu t=(1llu<<d[dep][i])+((1llu<<4)*(1llu<<d[dep][j]))+((1llu<<8)*(1llu<<d[dep][c[i]]))+((1llu<<12)*(1llu<<d[dep][c[j]]));
			llu p=((1llu<<(8*dep))*d[dep][i])+((1llu<<(8*dep+2))*d[dep][j])+((1llu<<(8*dep+4))*d[dep][c[i]])+((1llu<<(8*dep+6))*d[dep][c[j]]);
			n+=t;
			k+=p;
			DFS(dep-1);
			n-=t;
			k-=p;
		}
	}
}
int main() {
	for(int i=0;i<4;i++) {
		string t;
		cin>>t;
		for(int j=0;j<6;j++) {
			if(t[j]=='R') d[i][j]=0;
			if(t[j]=='G') d[i][j]=1;
			if(t[j]=='B') d[i][j]=2;
			if(t[j]=='Y') d[i][j]=3;
		}
	}
	for(int i=0;i<6;i+=2) {
		o=d[3][r[i]];
		//cout<<o<<"\n";
		llu w=((1llu<<d[3][r[(i+1)%6]])+((1llu<<4)*(1llu<<d[3][r[(i+2)%6]]))+((1llu<<8)*(1llu<<d[3][r[(i+4)%6]]))+((1llu<<12)*(1llu<<d[3][r[(i+5)%6]])));
		llu x=((1llu<<(8*3))*d[3][r[(i+1)%6]])+((1llu<<(8*3+2))*d[3][r[(i+2)%6]])+((1llu<<(8*3+4))*d[3][r[(i+4)%6]])+((1llu<<(8*3+6))*d[3][r[(i+5)%6]]);
		n+=w;
		k+=x;
		DFS(2);
		n-=w;
		k-=x;
	}
    for(int i=1;i<6;i+=2) {
		o=d[3][r[i]];
		//cout<<o<<"\n";
		llu w=((1llu<<d[3][r[(i-1)%6]])+((1llu<<4)*(1llu<<d[3][r[(i+1)%6]]))+((1llu<<8)*(1llu<<d[3][r[(i+2)%6]]))+((1llu<<12)*(1llu<<d[3][r[(i+4)%6]])));
		llu x=((1llu<<(8*3))*d[3][r[(i-1)%6]])+((1llu<<(8*3+2))*d[3][r[(i+1)%6]])+((1llu<<(8*3+4))*d[3][r[(i+2)%6]])+((1llu<<(8*3+6))*d[3][r[(i+4)%6]]);
		n+=w;
		k+=x;
		DFS(2);
		n-=w;
		k-=x;
	}
	cout<<cnt;
}

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다.

soloplay 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말