백준알고리즘

연구소

먼지의삶 2019. 10. 4. 22:40

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
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<utility>
 
using namespace std;
 
int map[8][8];
bool d[8][8];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int r, c;
vector<pair<int, int> > v;
vector<pair<int, int> > virus;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    int wall = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {
                virus.push_back(make_pair(i,j));
            }
            else if (map[i][j] == 0) {
                v.push_back(make_pair(i, j));
            }
            else if(map[i][j]==1)
                wall++;
        }
    }
    wall += 3;
    vector<int> seq;
    for (int i = 0; i < v.size(); i++) {
        if (i > v.size() - 4) {
            seq.push_back(1);
        }
        else {
            seq.push_back(0);
        }
    }
    int ans = r* c-wall;
    do {
        for (int i = 0; i < seq.size();  i++) {
            if (seq[i] == 1) {
                d[v[i].first][v[i].second] = true;
            }
        }
        int cnt = 0;
        queue<pair<int, int> > q;
        for (int i = 0; i < virus.size(); i++) {
            q.push(make_pair(virus[i].first, virus[i].second));
            d[virus[i].first][virus[i].second] = true;
            cnt++;
        }
        while (!q.empty()) {
            int x = q.front().first; int y = q.front().second;
            if (cnt > ans) break;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; int ny = y + dy[i];
                if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                    if (d[nx][ny] == false &&map[nx][ny] == 0) {
                        q.push(make_pair(nx, ny));
                        d[nx][ny] = true;
                        cnt++;
                        
                    }
                }
            }
        }
        
        if (ans > cnt) ans = cnt;
        memset(d, false, sizeof(d));
    } while (next_permutation(seq.begin(), seq.end()));
    cout << r*c - ans-wall << '\n';
    
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  

8x8 배열이라 조합으로 풀수있는문제가 아닌가싶다

조금만커져도 절대로 브루트포스로 풀수없는문제.

뭐 맵을 기억하고 하는것을 사용하는사람도 많은데.. 그냥 bool배열 매번초기화하는것과, 벽세울곳을 true로 놓고 다센뒤 초기화 되는것을 생각하면, 그리 시간이오래걸리지않는모양이다