15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
시간, 메모리 순위
숏코딩 순위
#include <stdio.h>
#include <iostream>
#include <string.h>
short N, M;
short map[10][10];
bool vst[9][10][10];
short dir[5][4][4] = { { { 0 },{ 1 },{ 2 },{ 3 } },{ { 0, 2 },{ 1,3 } },{ { 0,1 },{ 1,2 },{ 2,3 },{ 3,0 } },{ { 0,1,2 },{ 1,2,3 },{ 2,3,0 },{ 3,0,1 } },{ { 0,1,2,3 } } }; //카메라 번호, 회전, 개별 인덱스
short rot[5] = { 4, 2, 4, 4, 1 }; // 카메라 번호
short side[5] = { 1, 2, 2, 3, 4 };
short camn;
short cam[100];
short pos[100][2];
short walln, area, ans = 64;
short dr[] = { -1, 0, 1, 0 };
short dc[] = { 0, 1, 0, -1 };
void BF(short i, short sum) {
if (i == camn) {
if (sum < ans) {
ans = sum;
}
return;
}
for (short j = 0; j < rot[cam[i]]; ++j) {
memcpy(vst[i + 1], vst[i], 100);
short thisSum = 0;
for (short k = 0; k < side[cam[i]]; ++k) {
short d = dir[cam[i]][j][k];
for (short r = pos[i][0], c = pos[i][1]; map[r][c] != 6; r += dr[d], c += dc[d]) {
if (!vst[i + 1][r][c]) {
vst[i + 1][r][c] = 1;
++thisSum;
}
}
}
BF(i + 1, sum - thisSum);
}
}
int main() {
scanf("%hi%hi", &N, &M);
std::fill(map[0], map[0] + M + 2, 6);
for (short r = 1; r <= N; ++r) {
map[r][0] = map[r][M + 1] = 6;
for (short c = 1; c <= M; ++c) {
scanf("%hi", map[r] + c);
if (map[r][c] == 6) {
++walln;
}
else if (map[r][c]) {
cam[camn] = map[r][c] - 1;
pos[camn][0] = r;
pos[camn][1] = c;
++camn;
}
}
}
std::fill(map[N + 1], map[N + 1] + M + 2, 6);
BF(0, N * M - walln);
printf("%hi", ans);
return 0;
}