14939 불끄기
알고리즘(브루트, 그리디, 비트마스킹)
1
2
3
4
5
1. 최소한으로 눌러야하는 경우 : 한 칸은 한번만 눌러야함. 두번 이상누르면 최소가 아니고, 무한 루프가 될 수 잇음
2. 모든 방법을 다 검사해봐야 정답을 얻을 수 있음 -> 브루트 포스
3. 한번씩만 누르면 누르는 순서는 중요하지않음 -> 첫줄부터 차례대로 누름
4. 이때 첫번째줄은 모든 경우로 누른다고 치고, 두번째 줄부터는 위에 전구가 켜진 경우만 눌러도 해결이 가능하다. -> 그리디
5. 모든 경우는 0~1023까지 비트마스킹 방식으로 누르자 -> 비트마스킹
코드
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
#include <bits/stdc++.h>
using namespace std;
bool smap[10][10], tempMap[10][10];
int brute();
int rest();
void swit(int r, int c);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
for (int i = 0; i < 10; i++) {
char t;
for (int j = 0; j < 10; j++) {
cin >> t;
if (t == '#')
smap[i][j] = 0;
else if (t == 'O')
smap[i][j] = 1;
}
}
int result = brute();
if (result >= 2000000000)
cout << -1;
else
cout << result;
}
int brute() {
int result = 2000000000;
for (int i = 0; i <= 1023; i++) {
memcpy(tempMap, smap, sizeof(smap));
int k = 0, count = 0;
for (int j = 512; j >= 1; j /= 2) {
if (i & j) {
swit(0, k);
count++;
}
k++;
}
int r = rest();
result = min(result, count + r);
}
return result;
}
int rest() {
int count = 0;
for (int i = 1; i < 10; i++)
for (int j = 0; j < 10; j++)
if (tempMap[i - 1][j]) {
swit(i, j);
count++;
}
for (int j = 0; j < 10; j++) {
if (tempMap[9][j])
count = 2000000000;
}
return count;
}
void swit(int r, int c) {
tempMap[r][c] = !(tempMap[r][c]);
if (r > 0)
tempMap[r - 1][c] = !(tempMap[r - 1][c]);
if (c < 9 )
tempMap[r][c + 1] = !(tempMap[r][c + 1]);
if (r < 9)
tempMap[r + 1][c] = !(tempMap[r + 1][c]);
if (c > 0)
tempMap[r][c - 1] = !(tempMap[r][c - 1]);
}