15683번 감시

https://www.acmicpc.net/problem/15683

 

오랜만에 풀어본 대표적인 구현 및 시뮬레이션 문제이다.

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 10

int Map[MAX][MAX];
int R, C, m[MAX][MAX], ans = INT32_MAX; 
int loop[6] = { 0, 4, 2, 4, 4, 1 };
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
vector<pair<int, int>> v;

bool chk(int Y, int X)
{
    return (0 <= Y && Y < R) && (0 <= X && X < C) && (m[Y][X] != 6);
}

// →:0, ↓:1, ←:2, ↑:3
void draw(int now_direction, int y, int x, int value) {

    while (chk(y + dy[now_direction], x + dx[now_direction]))
    {
        Map[y + dy[now_direction]][x + dx[now_direction]] += value;
        y += dy[now_direction];
        x += dx[now_direction];
    }
}

void situation(int cctv_number, int y, int x, int now_case, int value) {
    if (cctv_number == 1) {
        if (now_case == 0) {
            draw(0, y, x, value);
        }
        else if (now_case == 1) {
            draw(1, y, x, value);
        }
        else if (now_case == 2) {
            draw(2, y, x, value);
        }
        else if (now_case == 3) {
            draw(3, y, x, value);
        }
    }
    else if (cctv_number == 2) {
        if (now_case == 0) {
            draw(0, y, x, value);
            draw(2, y, x, value);
        }
        else if (now_case == 1) {
            draw(1, y, x, value);
            draw(3, y, x, value);
        }
    }
    else if (cctv_number == 3) {
        if (now_case == 0) {
            draw(0, y, x, value);
            draw(3, y, x, value);
        }
        else if (now_case == 1) {
            draw(0, y, x, value);
            draw(1, y, x, value);
        }
        else if (now_case == 2) {
            draw(1, y, x, value);
            draw(2, y, x, value);
        }
        else if (now_case == 3) {
            draw(2, y, x, value);
            draw(3, y, x, value);
        }
    }
    else if (cctv_number == 4) {
        if (now_case == 0) {
            draw(0, y, x, value);
            draw(2, y, x, value);
            draw(3, y, x, value);
        }
        else if (now_case == 1) {
            draw(0, y, x, value);
            draw(1, y, x, value);
            draw(3, y, x, value);
        }
        else if (now_case == 2) {
            draw(0, y, x, value);
            draw(1, y, x, value);
            draw(2, y, x, value);
        }
        else if (now_case == 3) {
            draw(1, y, x, value);
            draw(2, y, x, value);
            draw(3, y, x, value);
        }
    }
    else if (cctv_number == 5) {
        draw(0, y, x, value);
        draw(1, y, x, value);
        draw(2, y, x, value);
        draw(3, y, x, value);
    }
}

void print()
{
    printf("\n■■■■■■■■■■■■■■■■■\n");
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%2d ", Map[i][j]);
        }
        printf("\n");
    }
    printf("■■■■■■■■■■■■■■■■■\n");
}

void simulation(int n) {
    if (v.size() <= n) {

        //print();

        int cnt = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (Map[i][j] == 0) {
                    ++cnt;
                }
            }
        }

        ans = min(ans, cnt);

        return;
    }

    int cctv_number = m[v[n].first][v[n].second];

    for (int i = 0; i < loop[cctv_number]; i++) {
        situation(cctv_number, v[n].first, v[n].second, i, 10);
        simulation(n + 1);
        situation(cctv_number, v[n].first, v[n].second, i, -10);
    }
}

int main()
{
    cin.tie(0);

    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
            if (1 <= m[i][j] && m[i][j] <= 5) {
                v.push_back({ i, j });
            }
            Map[i][j] = m[i][j];
        }
    }

    simulation(0);

    printf("%d\n", ans);

    return 0;
}