[16985번] Maaaaaaaaaze

16985번: Maaaaaaaaaze

 

www.acmicpc.net

5*5판 5개를 쌓고, 각 판을 회전 시키면서 cube[0][0][0] 에서 cube[4][4][4]로 갈수 있는 최소경로를 구하는 문제다.

조합 + 3차원 bfs문제다.

1. 각 판들을 쌓을 순서를 순열로 정한다.

2. 순서를 정했으면 각 판들을 회전시키면서 큐브를 만든다.

3. 큐브가 완성되었으면 bfs

주의할 점은

1. 각 판들을 순서를 바꿔서 쌓을수 있다.

2. 각 판들은 시계, 반시계 방향으로 자유롭게 회전가능 하지만 뒤집기는 안된다.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define min(a,b) a<b?a:b
using namespace std;
struct pnt { int r, c, h; };
int map[5][5][5], map2[5][5][5];//[층][r][c]
int visit[5][5][5], arr[5][5][5];
int tmp[5][5];
int check[5];
int dr[] = { 0,0,1,-1,0,0 };
int dc[] = { 0,0,0,0,1,-1 };
int dh[] = { 1,-1,0,0,0,0 };
int perm[] = { 0,1,2,3,4 };
int ans = 987654321;

string originTable[1100000], spinTable[1100000];
int oriSize, spiSize;

bool chk(int r, int c, int h) {
	if (!(r < 0 || c < 0 || h < 0 || r >= 5 || c >= 5 || h >= 5)) return true;
	return false;
}

bool shpChk(string table[], int *table_size) {
	//테이블에 있는지 체크, 없으면 넣고 정렬
	string tmpShp = "";
	for (int f = 0; f < 5; f++) {
		for (int r = 0; r < 5; r++) {
			for (int c = 0; c < 5; c++) {
				tmpShp += to_string(map[f][r][c]);
			}
		}
	}
	if (!binary_search(table, table + *table_size, tmpShp)) {
		table[*table_size] = tmpShp;
		*table_size = *table_size + 1;
		sort(table, table + *table_size);
		return true;
	}
	else
		return false;
}

void go(queue<pnt>Q) {
	bool END = false;
	while (!Q.empty()) {
		int rr = Q.front().r;
		int cc = Q.front().c;
		int hh = Q.front().h;
		Q.pop();
		for (int d = 0; d < 6; d++) {
			int nr = rr + dr[d];
			int nc = cc + dc[d];
			int nh = hh + dh[d];
			if (chk(nr, nc, nh) && map[nh][nr][nc] == 1 && visit[nh][nr][nc] == 0) {
				visit[nh][nr][nc] = visit[hh][rr][cc] + 1;

				if ((nh == 4 && nr == 4 && nc == 4) || (visit[nh][nr][nc] > ans))
					return;

				Q.push({ nr,nc,nh });
			}
		}
	}
}

void spin(int f) {
	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 5; c++) {
			tmp[c][4 - r] = map[f][r][c];
		}
	}
	memcpy(map[f], tmp, sizeof(tmp));
}

void dfs(int dep) {
	if (dep == 5) {
		if (map[0][0][0] == 0) return;
        if (ans == 12) return;
		//if (!shpChk(&*spinTable, &spiSize)) return;
		queue<pnt>Q;
		Q.push({ 0,0,0 });
		visit[0][0][0] = 1;
		go(Q);

		if (visit[4][4][4] > 0)
			ans = min(ans, visit[4][4][4] - 1);

		memcpy(visit, arr, sizeof(visit));
		return;
	}
	else {
		for (int i = 0; i < 4; i++) {
			spin(dep);
			dfs(dep + 1);
		}
	}
}

void stack(int idx) {
	if (idx == 5) {
		for (int i = 0; i < 5; i++)
			memcpy(map[i], map2[perm[i]], sizeof(map[i]));
		//여기서 전체 모양이 중복되는지 체크?
		if (shpChk(&*originTable, &oriSize)) dfs(0);
		return;
	}
	for (int i = idx; i < 5; i++) {
		swap(perm[i], perm[idx]);
		stack(idx + 1);
		swap(perm[i], perm[idx]);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	for (int f = 0; f < 5; f++)
		for (int r = 0; r < 5; r++)
			for (int c = 0; c < 5; c++)
				cin >> map2[f][r][c];
	//쌓아보기
	stack(0);
	if (ans == 987654321) ans = -1;
	cout << ans;
	return 0;
}