백준10218 Maze

작성일 | In

문제 링크

  • http://icpc.me/10218

문제 출처

  • Coder’s High 2014 E번

시간복잡도

  • $O(4 * 3^{10} * NM)$

풀이

10번 안에 뺄 수 있는지만 판단하면 되므로 $4^{10}$가지의 경우의 수를 모두 확인해주면 됩니다.
하지만 같은 방향으로 연속해서 2번 기울일 필요는 없기 때문에 경우의 수가 $4 * 3^{10}$으로 줄어들게 됩니다.
구현이 많이 귀찮지만, 열심히 구현하면 맞을 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

char c[] = "LRUD";
int di[] = {0, 0, -1, 1};
int dj[] = {-1, 1, 0, 0};
char arr[11][11];
int n, m;

void solve(){
    cin >> n >> m;
    vector<int> v; //.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
            if(arr[i][j] == '.') v.push_back(i*10+j);
        }
    }

    map<vector<int>, string> mp;
    mp[v] = "";
    queue<vector<int>> q; q.push(v);
    bool flag = 0;

    for(int idx=0; idx<10; idx++){
        int sz = q.size();
        while(sz--){
            auto now = q.front(); q.pop();
            string bit = mp[now]; bit += ".";
            for(int k=0; k<4; k++){
                if(bit[bit.size()-2] == c[k]) continue;
                vector<int> nxt;
                bit[idx] = c[k];
                for(auto pos : now){
                    int i = pos / 10, j = pos % 10;
                    while(arr[i][j] == '.') i += di[k], j += dj[k];
                    if(arr[i][j] == '#'){
                        i -= di[k]; j -= dj[k]; nxt.push_back(i*10+j);
                    }
                }
                if(nxt.empty()){
                    cout << bit << "\n"; flag = 1; break;
                }
                if(!mp.count(nxt)){
                    mp[nxt] = bit; q.push(nxt);
                }
            }
            if(flag) break;
        }
        if(flag) break;
    }
    if(!flag) cout << "XHAE\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
}