티스토리 뷰

백준 온라인 저지

190301 BOJ 16985번 Maaaaaaaaaze

Stolen Moments 2019. 3. 2. 01:12

브루트 포스


- 문제를 제대로 안읽어서 헤멨다.

- 회전 뿐만 아니라 층도 바꿀 수 있다는 것을 놓쳤다...



풀이 - 정확히 구현!




소스 코드 - 재귀 이용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <queue>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX 2147000000
using namespace std;
struct info {
    int x, y, z, cnt;
};
int ans = MAX;
int maze[5][5][5], check[5][5][5], A[5][5], B[5][5], C[5][5], D[5][5], E[5][5];
int dx[6] = { 1,0,-1,0,0,0 };
int dy[6] = { 0,1,0,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
int per[5] = { 0,1,2,3,4 };
int st[8][3] = { {0,0,0}, {4,0,0}, {0,4,0}, {0,0,4}, {4,4,0}, {0,4,4}, {4,0,4}, {4,4,4} };
int ed[8][3] = { {4,4,4}, {0,4,4}, {4,0,4}, {4,4,0}, {0,0,4}, {4,0,0}, {0,4,0}, {0,0,0} };
 
void init() {
    FOR(k, 0, 5) FOR(i, 0, 5) FOR(j, 0, 5) check[i][j][k] = 0;
}
 
 
void rotate(int k) {
    for (int i = 0; i < 2; i++) {
        for (int j = i; j < 4 - i; j++) {
            int temp = maze[i][j][k];
            maze[i][j][k] = maze[4 - j][i][k];
            maze[4 - j][i][k] = maze[4 - i][4 - j][k];
            maze[4 - i][4 - j][k] = maze[j][4 - i][k];
            maze[j][4 - i][k] = temp;
        }
    }
}
 
void solve(int floor) {
    if (floor == 5) {
        if (ans == 12) return;
        info point;
        queue<info> q;
        FOR(k, 0, 8) {
            point.x = st[k][0], point.y = st[k][1], point.z = st[k][2], point.cnt = 0;
            if (maze[point.x][point.y][point.z] == 0 || maze[ed[k][0]][ed[k][1]][ed[k][2]] == 0) continue;
            check[point.x][point.y][point.z] = 1;
            q.push(point);
            while (!q.empty()) {
                info now = q.front();
                q.pop();
                int x = now.x;
                int y = now.y;
                int z = now.z;
                int cnt = now.cnt;
                if (x == ed[k][0] && y == ed[k][1] && z == ed[k][2]) {
                    ans = min(ans, now.cnt);
                    if (ans == 12) {
                        cout << 12;
                        exit(0);
                    }
                    break;
                }
                FOR(i, 0, 6) {
                    int xx = x + dx[i];
                    int yy = y + dy[i];
                    int zz = z + dz[i];
                    if (xx < 0 || xx >= 5 || yy < 0 || yy >= 5 || zz < 0 || zz >= 5) continue;
                    if (check[xx][yy][zz] == 0 && maze[xx][yy][zz] == 1) {
                        check[xx][yy][zz] = 1;
                        now.x = xx;
                        now.y = yy;
                        now.z = zz;
                        now.cnt = cnt + 1;
                        q.push(now);
                    }
                }
            }
            while (!q.empty()) q.pop();
            init();
        }
    }
    else {
        FOR(i, 0, 5) {
            if (ans == 12) return;
            rotate(floor);
            solve(floor + 1);
        }
    }
}
 
int main() {
    sws;
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> A[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> B[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> C[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> D[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> E[i][j];
    
    do {
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[0]] = A[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[1]] = B[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[2]] = C[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[3]] = D[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[4]] = E[i][j];
        solve(0);
    } while (next_permutation(per, per + 5));
 
    if (ans != MAX) cout << ans;
    else cout << -1;
}
cs




소스 코드 - 다중 for문


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <queue>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX 2147000000
using namespace std;
struct info {
    int x, y, z, cnt;
};

int maze[5][5][5], check[5][5][5], A[5][5], B[5][5], C[5][5], D[5][5], E[5][5];
int dx[6] = { 1,0,-1,0,0,0 };
int dy[6] = { 0,1,0,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
int per[5] = { 0,1,2,3,4 };
int st[8][3] = { {0,0,0}, {4,0,0}, {0,4,0}, {0,0,4}, {4,4,0}, {0,4,4}, {4,0,4}, {4,4,4} };
int ed[8][3] = { {4,4,4}, {0,4,4}, {4,0,4}, {4,4,0}, {0,0,4}, {4,0,0}, {0,4,0}, {0,0,0} };

void init() {
    FOR(k, 0, 5) FOR(i, 0, 5) FOR(j, 0, 5) check[i][j][k] = 0;
}

void rotate(int k) {
    for (int i = 0; i < 2; i++) {
        for (int j = i; j < 4 - i; j++) {
            int temp = maze[i][j][k];
            maze[i][j][k] = maze[4 - j][i][k];
            maze[4 - j][i][k] = maze[4 - i][4 - j][k];
            maze[4 - i][4 - j][k] = maze[j][4 - i][k];
            maze[j][4 - i][k] = temp;
        }
    }
}

int main() {
    sws;
    int ans = MAX;
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> A[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> B[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> C[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> D[i][j];
    FOR(i, 0, 5) FOR(j, 0, 5) cin >> E[i][j];
    do {
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[0]] = A[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[1]] = B[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[2]] = C[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[3]] = D[i][j];
        FOR(i, 0, 5) FOR(j, 0, 5) maze[i][j][per[4]] = E[i][j];
        info point;
        queue<info> q;
        FOR(a, 0, 4) {
            rotate(0);
            FOR(b, 0, 4) {
                rotate(1);
                FOR(c, 0, 4) {
                    rotate(2);
                    FOR(d, 0, 4) {
                        rotate(3);
                        FOR(e, 0, 4) {
                            rotate(4);
                            FOR(k, 0, 8) {
                                point.x = st[k][0], point.y = st[k][1], point.z = st[k][2], point.cnt = 0;
                                if (maze[point.x][point.y][point.z] == 0 || maze[ed[k][0]][ed[k][1]][ed[k][2]] == 0) continue;
                                check[point.x][point.y][point.z] = 1;
                                q.push(point);
                                while (!q.empty()) {
                                    info now = q.front();
                                    q.pop();
                                    int x = now.x;
                                    int y = now.y;
                                    int z = now.z;
                                    int cnt = now.cnt;
                                    if (x == ed[k][0] && y == ed[k][1] && z == ed[k][2]) {
                                        ans = min(ans, now.cnt);
                                        if (ans == 12) goto END;
                                        break;
                                    }
                                    FOR(i, 0, 6) {
                                        int xx = x + dx[i];
                                        int yy = y + dy[i];
                                        int zz = z + dz[i];
                                        if (xx < 0 || xx >= 5 || yy < 0 || yy >= 5 || zz < 0 || zz >= 5) continue;
                                        if (check[xx][yy][zz] == 0 && maze[xx][yy][zz] == 1) {
                                            check[xx][yy][zz] = 1;
                                            now.x = xx;
                                            now.y = yy;
                                            now.z = zz;
                                            now.cnt = cnt + 1;
                                            q.push(now);
                                        }
                                    }
                                }
                                while (!q.empty()) q.pop();
                                init();
                            }
                        }
                    }
                }
            }
        }
    } while (next_permutation(per, per + 5));
    
    END:
    if (ans != MAX) cout << ans;
    else cout << -1;
}
cs



반응형
저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

190316 BOJ 1018번 체스판 다시 칠하기  (0) 2019.03.16
190305 BOJ 9370번 미확인 도착지  (0) 2019.03.05
190224 BOJ 1406번 에디터  (0) 2019.02.25
190217 BOJ 14500번 테트로미노  (0) 2019.02.17
190217 BOJ 1208번 부분집합의 합 2  (0) 2019.02.17
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
글 보관함