반응형
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
|
void dfs(int x, int y, int idx) {
if (idx == cnt) {
ans = min(ans, zeros());
return;
}
int rotate = 4;
int i = cctvs[idx].first;
int j = cctvs[idx].second;
int cctv = arr[i][j];
if (cctv == -2)
rotate = 2;
else if (cctv == -5)
rotate = 1;
rep(k, rotate) {
look(i, j, cctv, k, 1);
visited[i][j] = 1;
dfs(i, j, idx+1);
visited[i][j] = 0;
look(i, j, cctv, k, 0);
}
}
|
cs |
|
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
|
void look(int x, int y, int cctv, int direction, int cmd) {
// direction: 0, 1, 2, 3
if (cctv == -1) {
lookDirection(x, y, direction, cmd);
}
// direction: 0, 1
else if (cctv == -2) {
lookDirection(x, y, direction, cmd);
lookDirection(x, y, (direction+2)%4, cmd);
}
// direction: 0, 1, 2, 3
else if (cctv == -3) {
lookDirection(x, y, direction, cmd);
lookDirection(x, y, (direction + 1) % 4, cmd);
}
// direction: 0, 1, 2, 3
else if (cctv == -4) {
lookDirection(x, y, direction, cmd);
lookDirection(x, y, (direction + 1) % 4, cmd);
lookDirection(x, y, (direction + 2) % 4, cmd);
}
// direction:
else if (cctv == -5) {
lookDirection(x, y, 0, cmd);
lookDirection(x, y, 1, cmd);
lookDirection(x, y, 2, cmd);
lookDirection(x, y, 3, cmd);
}
}
|
cs |
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 | #include <iostream> #include <algorithm> #define pii pair<int, int> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; int n, m, arr[9][9], temp, ans= 987654321; pii cctvs[9]; int cnt; bool visited[9][9]; void lookDirection(int x, int y, int direction, int cmd) { while (x >= 0 && x < n && y >= 0 && y < m) { if (arr[x][y] == -6) break; if (arr[x][y] < 0) { if (direction == 0) y++; else if (direction == 1) x++; else if (direction == 2) y--; else if (direction == 3) x--; continue; } // 우 if (direction == 0) { if (cmd) arr[x][y++]++; else arr[x][y++]--; } // 하 else if (direction == 1) { if (cmd) arr[x++][y]++; else arr[x++][y]--; } // 좌 else if (direction == 2) { if (cmd) arr[x][y--]++; else arr[x][y--]--; } // 상 else if (direction == 3) { if (cmd) arr[x--][y]++; else arr[x--][y]--; } } } void look(int x, int y, int cctv, int direction, int cmd) { // direction: 0, 1, 2, 3 if (cctv == -1) { lookDirection(x, y, direction, cmd); } // direction: 0, 1 else if (cctv == -2) { lookDirection(x, y, direction, cmd); lookDirection(x, y, (direction+2)%4, cmd); } // direction: 0, 1, 2, 3 else if (cctv == -3) { lookDirection(x, y, direction, cmd); lookDirection(x, y, (direction + 1) % 4, cmd); } // direction: 0, 1, 2, 3 else if (cctv == -4) { lookDirection(x, y, direction, cmd); lookDirection(x, y, (direction + 1) % 4, cmd); lookDirection(x, y, (direction + 2) % 4, cmd); } // direction: else if (cctv == -5) { lookDirection(x, y, 0, cmd); lookDirection(x, y, 1, cmd); lookDirection(x, y, 2, cmd); lookDirection(x, y, 3, cmd); } } int zeros() { int ret = 0; rep(i, n) { rep(j, m) if (arr[i][j] == 0) ret++; } return ret; } void dfs(int x, int y, int idx) { if (idx == cnt) { ans = min(ans, zeros()); return; } int rotate = 4; int i = cctvs[idx].first; int j = cctvs[idx].second; int cctv = arr[i][j]; if (cctv == -2) rotate = 2; else if (cctv == -5) rotate = 1; rep(k, rotate) { look(i, j, cctv, k, 1); visited[i][j] = 1; dfs(i, j, idx+1); visited[i][j] = 0; look(i, j, cctv, k, 0); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; rep(i, n) { rep(j, m) { cin >> temp; arr[i][j] = temp * -1; // arr[i][j]: cctv가 감시 가능한 영역이면 + 1 if(temp>=1&&temp<=5) // cctv 번호, 벽과 겹칠 수 있으므로, (입력) * -1 해서 음수로 저장 cctvs[cnt++] = { i,j }; } } dfs(0, 0, 0); cout << ans; } | cs |
반응형