問題: BOJ 15683 — 監視 · 한국어 · English
CCTVは種類ごとに定められた方向を監視し、90度ずつ回転できます。タイプ1は1方向、タイプ2は互いに反対の2方向、タイプ3は隣り合う2方向、タイプ4は3方向、タイプ5は4方向すべてを監視します。異なる向きの数はそれぞれ4、2、4、4、1通りです。監視の光線はほかのCCTVや空きマスを通過しますが、壁または盤面の端で止まります。
深さ優先探索で各CCTVの向きを1つずつ選び、すべての組み合わせを調べます。向きの組み合わせが決まったら、新しい監視配列に各方向の光線を記録し、監視されない空きマスの数を数えます。その最小値を答えとします。壁とCCTVは死角に数えないため、値が0のマスだけを数えます。CCTVは最大8台なので、組み合わせ数は最大4^8です。各組み合わせで光線を追跡してマスを数えるのにO(NM)かかるため、全体の時間計算量はO(4^8 NM)、追加領域計算量はO(NM)です。
C++17
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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Camera {
int row;
int column;
int type;
};
int n, m;
vector<vector<int>> board;
vector<Camera> cameras;
vector<int> orientation;
int minimumBlindSpots;
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
const vector<vector<int>> directions[5] = {
{{0}, {1}, {2}, {3}},
{{0, 2}, {1, 3}},
{{0, 1}, {1, 2}, {2, 3}, {3, 0}},
{{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {0, 2, 3}},
{{0, 1, 2, 3}}
};
void evaluate() {
vector<vector<bool>> watched(n, vector<bool>(m, false));
for (int i = 0; i < static_cast<int>(cameras.size()); ++i) {
const Camera& camera = cameras[i];
const auto& dirs = directions[camera.type - 1][orientation[i]];
for (int dir : dirs) {
int row = camera.row + dr[dir];
int column = camera.column + dc[dir];
while (row >= 0 && row < n && column >= 0 && column < m && board[row][column] != 6) {
watched[row][column] = true;
row += dr[dir];
column += dc[dir];
}
}
}
int blindSpots = 0;
for (int row = 0; row < n; ++row) {
for (int column = 0; column < m; ++column) {
if (board[row][column] == 0 && !watched[row][column]) ++blindSpots;
}
}
minimumBlindSpots = min(minimumBlindSpots, blindSpots);
}
void search(int index) {
if (index == static_cast<int>(cameras.size())) {
evaluate();
return;
}
const int type = cameras[index].type;
const int count = static_cast<int>(directions[type - 1].size());
for (int turn = 0; turn < count; ++turn) {
orientation[index] = turn;
search(index + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
board.assign(n, vector<int>(m));
for (int row = 0; row < n; ++row) {
for (int column = 0; column < m; ++column) {
cin >> board[row][column];
if (1 <= board[row][column] && board[row][column] <= 5) {
cameras.push_back({row, column, board[row][column]});
}
}
}
orientation.resize(cameras.size());
minimumBlindSpots = n * m;
search(0);
cout << minimumBlindSpots << '\n';
}