제목 링크:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2477
acm 를 접 한 후부 터 지금까지 ZOJ 의 문제 에 저촉 되 었 습 니 다.제 가 했 던 많은 ZOJ 의 문 제 는 대부분 주제 의 뜻 이 모호 하고 설명 이 잘 되 지 않 았 습 니 다.
이 문제 의 난점 은 검색 이 아니 라 문 제 를 보 는 질문 법 만 봐 도 교체 로 깊 어 지 는 것 임 을 알 아야 하지만 정 작 사람 을 무 너 뜨리 는 곳 은 어디 일 까?
먼저 큐 브 의 전개 도,어느 면 이 정면 이나 뒷면 인지 가리 키 지 않 으 면 대응 하 는 시계 반대 방향 도 달라 지 는데 제목 설명 이 없 으 면 어 떡 하 죠?어 쩌 겠 어 요?저 는 해 봐 야 겠 어 요.제 가 먼저 색인 을 1 로 하 는 이 면 을 입방 의 뒷면 으로 한 다음 에 시계 반대 방향 으로 회전 하 는 것 을 모 의 했 어 요.계속 WA 를 했 어 요.그리고 WA 의 원인 이 시계 반대 방향 인지 다른 곳 에서 잘 쓰 지 못 했 는 지 확신 할 수 없어 요.제 가 색인 을 1 로 하 는 이 면 을 정면 으로 할 때 시 뮬 레이 션 시계 반대 방향 코드 를 다시 수정 하면 AC 예요.정말 할 말 이 없다.
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int Maxn = 4e5+10;
int cube[10][4][4];
bool check() {
for(int i = 0; i < 6; ++i) {
int tmp = cube[i][0][0];
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) if(tmp != cube[i][j][k]) {
return false;
}
}
}
return true;
}
void Size(int x, int dir) {
if(dir == 1) {
swap(cube[x][0][0], cube[x][0][2]);
swap(cube[x][0][0], cube[x][2][2]);
swap(cube[x][0][0], cube[x][2][0]);
swap(cube[x][0][1], cube[x][1][2]);
swap(cube[x][0][1], cube[x][2][1]);
swap(cube[x][0][1], cube[x][1][0]);
} else {
swap(cube[x][0][0], cube[x][2][0]);
swap(cube[x][0][0], cube[x][2][2]);
swap(cube[x][0][0], cube[x][0][2]);
swap(cube[x][0][1], cube[x][1][0]);
swap(cube[x][0][1], cube[x][2][1]);
swap(cube[x][0][1], cube[x][1][2]);
}
}
void solve(int x, int dir) {
Size(x, dir);
if(x == 1 && dir == 1) { //
swap(cube[4][2][0], cube[2][0][0]); swap(cube[4][2][2], cube[2][2][0]);
swap(cube[4][2][0], cube[5][0][2]); swap(cube[4][2][2], cube[5][0][0]);
swap(cube[4][2][0], cube[0][2][2]); swap(cube[4][2][2], cube[0][0][2]);
swap(cube[4][2][1], cube[2][1][0]);
swap(cube[4][2][1], cube[5][0][1]);
swap(cube[4][2][1], cube[0][1][2]);
} else if(x == 1 && dir == -1) {
swap(cube[4][2][0], cube[0][2][2]); swap(cube[4][2][2], cube[0][0][2]);
swap(cube[4][2][0], cube[5][0][2]); swap(cube[4][2][2], cube[5][0][0]);
swap(cube[4][2][0], cube[2][0][0]); swap(cube[4][2][2], cube[2][2][0]);
swap(cube[4][2][1], cube[0][1][2]);
swap(cube[4][2][1], cube[5][0][1]);
swap(cube[4][2][1], cube[2][1][0]);
}
if(x == 3 && dir == -1) { //
swap(cube[4][0][0], cube[2][0][2]); swap(cube[4][0][2], cube[2][2][2]);
swap(cube[4][0][0], cube[5][2][2]); swap(cube[4][0][2], cube[5][2][0]);
swap(cube[4][0][0], cube[0][2][0]); swap(cube[4][0][2], cube[0][0][0]);
swap(cube[4][0][1], cube[2][1][2]);
swap(cube[4][0][1], cube[5][2][1]);
swap(cube[4][0][1], cube[0][1][0]);
} else if(x == 3 && dir == 1) {
swap(cube[4][0][0], cube[0][2][0]); swap(cube[4][0][2], cube[0][0][0]);
swap(cube[4][0][0], cube[5][2][2]); swap(cube[4][0][2], cube[5][2][0]);
swap(cube[4][0][0], cube[2][0][2]); swap(cube[4][0][2], cube[2][2][2]);
swap(cube[4][0][1], cube[0][1][0]);
swap(cube[4][0][1], cube[5][2][1]);
swap(cube[4][0][1], cube[2][1][2]);
}
if(x == 2 && dir == -1) { //
swap(cube[3][0][0], cube[4][2][2]); swap(cube[3][2][0], cube[4][0][2]);
swap(cube[3][0][0], cube[1][2][2]); swap(cube[3][2][0], cube[1][0][2]);
swap(cube[3][0][0], cube[5][2][2]); swap(cube[3][2][0], cube[5][0][2]);
swap(cube[3][1][0], cube[4][1][2]);
swap(cube[3][1][0], cube[1][1][2]);
swap(cube[3][1][0], cube[5][1][2]);
} else if(x == 2 && dir == 1) {
swap(cube[3][0][0], cube[5][2][2]); swap(cube[3][2][0], cube[5][0][2]);
swap(cube[3][0][0], cube[1][2][2]); swap(cube[3][2][0], cube[1][0][2]);
swap(cube[3][0][0], cube[4][2][2]); swap(cube[3][2][0], cube[4][0][2]);
swap(cube[3][1][0], cube[5][1][2]);
swap(cube[3][1][0], cube[1][1][2]);
swap(cube[3][1][0], cube[4][1][2]);
}
if(x == 0 && dir == 1) { //
swap(cube[3][0][2], cube[4][2][0]); swap(cube[3][2][2], cube[4][0][0]);
swap(cube[3][0][2], cube[1][2][0]); swap(cube[3][2][2], cube[1][0][0]);
swap(cube[3][0][2], cube[5][2][0]); swap(cube[3][2][2], cube[5][0][0]);
swap(cube[3][1][2], cube[4][1][0]);
swap(cube[3][1][2], cube[1][1][0]);
swap(cube[3][1][2], cube[5][1][0]);
} else if(x == 0 && dir == -1) {
swap(cube[3][0][2], cube[5][2][0]); swap(cube[3][2][2], cube[5][0][0]);
swap(cube[3][0][2], cube[1][2][0]); swap(cube[3][2][2], cube[1][0][0]);
swap(cube[3][0][2], cube[4][2][0]); swap(cube[3][2][2], cube[4][0][0]);
swap(cube[3][1][2], cube[5][1][0]);
swap(cube[3][1][2], cube[1][1][0]);
swap(cube[3][1][2], cube[4][1][0]);
}
if(x == 5 && dir == -1) { //
swap(cube[3][2][0], cube[2][2][0]); swap(cube[3][2][2], cube[2][2][2]);
swap(cube[3][2][0], cube[1][2][0]); swap(cube[3][2][2], cube[1][2][2]);
swap(cube[3][2][0], cube[0][2][0]); swap(cube[3][2][2], cube[0][2][2]);
swap(cube[3][2][1], cube[2][2][1]);
swap(cube[3][2][1], cube[1][2][1]);
swap(cube[3][2][1], cube[0][2][1]);
} else if(x == 5 && dir == 1) {
swap(cube[3][2][0], cube[0][2][0]); swap(cube[3][2][2], cube[0][2][2]);
swap(cube[3][2][0], cube[1][2][0]); swap(cube[3][2][2], cube[1][2][2]);
swap(cube[3][2][0], cube[2][2][0]); swap(cube[3][2][2], cube[2][2][2]);
swap(cube[3][2][1], cube[0][2][1]);
swap(cube[3][2][1], cube[1][2][1]);
swap(cube[3][2][1], cube[2][2][1]);
}
if(x == 4 && dir == -1) { //
swap(cube[0][0][0], cube[1][0][0]); swap(cube[0][0][2], cube[1][0][2]);
swap(cube[0][0][0], cube[2][0][0]); swap(cube[0][0][2], cube[2][0][2]);
swap(cube[0][0][0], cube[3][0][0]); swap(cube[0][0][2], cube[3][0][2]);
swap(cube[0][0][1], cube[1][0][1]);
swap(cube[0][0][1], cube[2][0][1]);
swap(cube[0][0][1], cube[3][0][1]);
} else if(x == 4 && dir == 1) {
swap(cube[0][0][0], cube[3][0][0]); swap(cube[0][0][2], cube[3][0][2]);
swap(cube[0][0][0], cube[2][0][0]); swap(cube[0][0][2], cube[2][0][2]);
swap(cube[0][0][0], cube[1][0][0]); swap(cube[0][0][2], cube[1][0][2]);
swap(cube[0][0][1], cube[3][0][1]);
swap(cube[0][0][1], cube[2][0][1]);
swap(cube[0][0][1], cube[1][0][1]);
}
}
int ans[10][2], cnt;
void print() {
for(int i = 0; i < 6; ++i) {
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) cout << cube[i][j][k] << " ";
cout << endl;
}
cout << endl;
}
}
bool dfs(int dep, int step) {
if(check()) return true;
if(step == dep) return false;
for(int i = 0; i < 6; ++i) {
ans[cnt][0] = i; ans[cnt][1] = -1;
cnt++; solve(i, -1);
if(dfs(dep, step+1)) return true;
cnt--; solve(i, 1);
ans[cnt][0] = i; ans[cnt][1] = 1;
cnt++; solve(i, 1);
if(dfs(dep, step+1)) return true;
cnt--; solve(i, -1);
}
return false;
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--) {
int r = 0, c = 0;
while(r < 2 || c < 3) {
char ch = getchar();
if(c == 3) {
c = 0; r++;
}
if(ch >= 'a' && ch <= 'z') cube[4][r][c++] = ch-'a';
}
r = 0; c = 0;
while(r < 2 || c < 12) {
char ch = getchar();
if(c == 12) {
c = 0; r++;
}
if(ch < 'a' || ch > 'z') continue;
if(c < 3) cube[0][r][c] = ch-'a';
else if(c < 6) cube[1][r][c-3] = ch-'a';
else if(c < 9) cube[2][r][c-6] = ch-'a';
else cube[3][r][c-9] = ch-'a';
c++;
}
r = 0; c = 0;
while(r < 2 || c < 3) {
char ch = getchar();
if(c == 3) {
c = 0; r++;
}
if(ch >= 'a' && ch <= 'z') cube[5][r][c++] = ch-'a';
}
// print();
cnt = 0; bool ok = false;
for(int dep = 1; dep <= 5; ++dep) {
if(dfs(dep, 0)) {
ok = true; break;
}
}
if(!ok) printf("-1 ");
else {
printf("%d ", cnt);
for(int i = 0; i < cnt; ++i) printf("%d %d ", ans[i][0], ans[i][1]);
}
}
return 0;
}
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기
아이디어
Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고
sb에 고른 카드를 담도록 하였다.
이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.