Notice
Recent Posts
Recent Comments
Link
«   2025/04   »
일 월 화 수 목 금 토
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
Tags
more
Archives
Today
Total
관리 메뉴

찌로그

[BOJ] 백준 15683번 감시 2020_05_26 C++ 본문

Coding

[BOJ] 백준 15683번 감시 2020_05_26 C++

찌드 2020. 5. 26. 18:11

https://www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감��

www.acmicpc.net

 

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
 
using namespace std;
#define For(a,b,i) for(int i=a; i<b; i++)
typedef pair<int, int> p;
const int dy[4] = {-1,1,0,0};
const int dx[4] = {0,0,-1,1};
int n,m,answer=INT_MAX;
int og[8][8];
//vector<vector<p>> cams(7);
vector<p> cams;
void zeros(int maps[8][8]){
    int temp =0;
    For(0,n,i) For(0,m,j) if(maps[i][j] == 0) temp++;
    // For(0,n,i){
    //     For(0,m,j){
    //         if(maps[i][j] == -1) cout << "* " ;
    //         else cout << maps[i][j] << " ";
    //     }
    //     cout << endl;
 
    // }
    // cout << endl;
    answer = min(answer, temp);
}
 
void marking(int maps[8][8], p a, int i){
    p c = a;
    while(1){
        int ny = c.first+dy[i], nx = c.second+dx[i];
        if(ny >= n || ny<0 || nx >=m || nx<0) break;
        if(maps[ny][nx] == 6) break;
        if(maps[ny][nx] == 0) maps[ny][nx] = -1;
        c.first = ny, c.second = nx;
    }
}
 
void input(){
    cin >> n >> m;
    For(0,n,i){
        For(0,m,j){
            cin >> og[i][j];
            if(og[i][j] != 0 && og[i][j] != 6){
                cams.push_back({i,j});
            }
        }
    }
}
void dfs(int copied[8][8], int i){
    if(i == cams.size()){
        zeros(copied);
        return;
    }
    p q = cams[i];
    int cat = og[q.first][q.second];
    if(cat == 1){ // 4 cases
        int next[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]);
        marking(next,q,0);
        dfs(next,i+1);
 
        int next2[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]);
        marking(next2,q,1);
        dfs(next2,i+1);
 
        int next3[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]);
        marking(next3,q,2);
        dfs(next3,i+1);
 
        int next4[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]);
        marking(next4,q,3);
        dfs(next4,i+1);
    }
    else if(cat == 2){ // 2 cases
        int next[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]);
        marking(next,q,0); marking(next,q,1);
        dfs(next,i+1);
 
        int next2[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]);
        marking(next2,q,2); marking(next2,q,3);
        dfs(next2,i+1);
    }else if(cat == 3){ // 4 casses
        int next[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]);
        marking(next,q,0); marking(next,q,3);
        dfs(next,i+1);
 
        int next2[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]);
        marking(next2,q,1); marking(next2,q,3);
        dfs(next2,i+1);
 
        int next3[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]);
        marking(next3,q,1); marking(next3,q,2);
        dfs(next3,i+1);
 
        int next4[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]);
        marking(next4,q,0); marking(next4,q,2);
        dfs(next4,i+1);
    }else if(cat == 4){ // 4 casses
        int next[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]);
        marking(next,q,0); marking(next,q,2); marking(next,q,3);
        dfs(next,i+1);
 
        int next2[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]);
        marking(next2,q,1); marking(next2,q,2); marking(next2,q,3);
        dfs(next2,i+1);
 
        int next3[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]);
        marking(next3,q,0); marking(next3,q,1); marking(next3,q,2);
        dfs(next3,i+1);
 
        int next4[8][8];
        copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]);
        marking(next4,q,0); marking(next4,q,1); marking(next4,q,3);
        dfs(next4,i+1);
    }else if(cat == 5){
        For(0,4,i) marking(copied, q, i);
        dfs(copied,i+1);
    }
}
void solve(){
    dfs(og, 0);
    cout << answer <<endl;
 
}
int main(){
    input();
    solve();
    return 0;
}
 
cs

'Coding' 카테고리의 다른 글

[프로그래머스] level2 쇠막대기 2020_05_29 Python3  (0) 2020.05.29
[프로그래머스] level2 프린터 2020_05_29 Python3  (0) 2020.05.29
[BOJ] 백준 14891번 톱니바퀴 2020_05_22 C++  (0) 2020.05.22
[BOJ] 백준 14890번 경사로 2020_05_22 C++  (0) 2020.05.22
[BOJ] 백준 17825번 주사위 윷놀이 2020_05_21 C++  (0) 2020.05.21
'Coding' Related Articles more
Comments