BOJ 15683 — CCTV Surveillance

BOJ 15683: CCTV Surveillance · 한국어 · 日本語

Each CCTV type covers a fixed pattern of directions, which can be rotated by 90 degrees. Type 1 covers one direction, type 2 covers a pair of opposite directions, type 3 covers two adjacent directions, type 4 covers three directions, and type 5 covers all four. Their distinct orientations number 4, 2, 4, 4, and 1 respectively. A surveillance ray passes through other CCTVs and empty cells, but stops before a wall or the edge of the board.

Enumerate one orientation for each camera with depth-first search. At each complete assignment, trace every selected ray into a fresh visibility grid, then count the empty cells that remain unseen. Keep the minimum count. Walls and cameras are not blind spots, so only cells containing zero are included in the count. With at most eight cameras, there are at most 4^8 assignments; tracing all rays and counting cells costs O(NM) per assignment, for O(4^8 NM) time and O(NM) auxiliary space.

C++17

{% raw %}

#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';
}

{% endraw %}