백준17622 타일 교체

작성일 | In

문제 링크

  • http://icpc.me/17622

문제 출처

  • 2019 KOI 고등부 1번

시간복잡도

  • $O(N^4)$

풀이

$K = 0$인 경우에는 단순히 DFS/BFS를 수행하는 것으로 $O(N^2)$에 문제를 해결할 수 있습니다.

$K = 1$인 경우에는 타일을 바꿀 수 있는 모든 경우($5N^2$가지)에 대해 모두 DFS/BFS를 수행해보는 것으로 $O(N^4)$에 문제를 해결할 수 있습니다.

전체 코드

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

constexpr int INF = 0x3f3f3f3f;
constexpr int dx[6][2] = { {1,0}, {1,0}, {-1,0}, {-1,0}, {1,-1}, {0,0} };
constexpr int dy[6][2] = { {0,1}, {0,-1}, {0,1}, {0,-1}, {0,0}, {-1,1} };

vector<int> ableTile(int di, int dj){
    if(di == -1 && dj ==  0) return {0, 1, 4};
    if(di ==  1 && dj ==  0) return {2, 3, 4};
    if(di ==  0 && dj == -1) return {0, 2, 5};
    if(di ==  0 && dj ==  1) return {1, 3, 5};
    return {};
}

int N, K, A[55][55];
bool C[55][55];
bool bound(int i, int j){ return 1 <= i && i <= N && 1 <= j && j <= N && !C[i][j]; }

int Solve(){
    memset(C, 0, sizeof C);

    int st = false, ed = false;
    for(auto i : ableTile(0, +1)) if(A[1][1] == i) st = true;
    for(auto i : ableTile(0, -1)) if(A[N][N] == i) ed = true;
    if(!st || !ed) return INF;

    int i, j, cnt;
    for(i=1, j=1, cnt=1; bound(i, j); cnt++){
        if(i == N && j == N) break;
        C[i][j] = true;

        bool able = false;
        for(int iter=0; iter<2 && !able; iter++){
            int di = dx[A[i][j]][iter], dj = dy[A[i][j]][iter];
            if(!bound(i+di, j+dj)) continue;
            for(auto tile : ableTile(di, dj)) if(A[i+di][j+dj] == tile) {
                able = true; i += di; j += dj;
                break;
            }
        }
    }
    if(i == N && j == N) return cnt;
    return INF;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> A[i][j];

    if(K == 0){
        int res = Solve();
        if(res == INF) cout << -1;
        else cout << res;
        return 0;
    }

    int res = INF;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
        int now = A[i][j];
        for(int k=0; k<6; k++) if(now != k) {
            A[i][j] = k;
            res = min(res, Solve());
        }
        A[i][j] = now;
    }

    if(res == INF) cout << -1;
    else cout << res;
}