백준 15683번

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int MAX_INT = numeric_limits<int>::max();

int camStatus[8] = {0};
vector<int> camType;
vector<pair<int, int>> camLoc;
vector<int> choices = {-1, 4, 2, 4, 4, 1};
int N, M, C;
vector<vector<int>> map;

int min_blind = MAX_INT;

vector<vector<int>> dirs = {
    {0, 1},  // 오른쪽
    {-1, 0}, // 윗쪽
    {0, -1}, // 왼쪽
    {1, 0}}; // 아랫쪽

void mark(vector<vector<int>> &mm, int n, int m, int dir)
{
    // n,m을 기점으로 방향을 따라 쭉 감시가능한 구간을 표시함
    int cn = n + dirs[dir][0];
    int cm = m + dirs[dir][1];

    while (0 <= cn && cn < N && 0 <= cm && cm < M)
    {
        if (mm[cn][cm] == 6)
        {
            //벽을 만났으니 멈춤
            break;
        }

        if (mm[cn][cm] == 0)
        {
            // 빈 공간이니까 감시가 가능하다고 써줌
            // 만약 카메라면 안건드리고 그냥 넘어감
            mm[cn][cm] = 7; //7은 감시가 된다는 뜻
        }
        cn += dirs[dir][0];
        cm += dirs[dir][1];
    }

    return;
}

int calc(int until) // until번째 카메라까지 반영해서 사각지대의 갯수를 계산
{
    vector<vector<int>> tmap = map; // copy

    for (int i = 0; i <= until; i++)
    {
        int ctype = camType[i];
        int cStatus = camStatus[i];
        int n = camLoc[i].first;
        int m = camLoc[i].second;

        if (ctype == 1)
        {
            mark(tmap, n, m, cStatus);
        }
        else if (ctype == 2)
        {
            if (cStatus == 0)
            {
                mark(tmap, n, m, 0);
                mark(tmap, n, m, 2);
            }
            else if (cStatus == 1)
            {
                mark(tmap, n, m, 1);
                mark(tmap, n, m, 3);
            }
        }
        else if (ctype == 3)
        {
            int dd = (cStatus + 1) % 4;
            mark(tmap, n, m, cStatus);
            mark(tmap, n, m, dd);
        }
        else if (ctype == 4)
        {
            for (int d = 0; d < 4; d++)
            {
                if (d == cStatus)
                {
                    continue;
                }
                mark(tmap, n, m, d);
            }
        }
        else if (ctype == 5)
        {
            for (int d = 0; d < 4; d++)
            {
                mark(tmap, n, m, d);
            }
        }
    }

    int bcnt = 0;
    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            if (tmap[n][m] == 0)
            {
                bcnt++;
            }
        }
    }

    return bcnt;
}

void dfs(int depth)
{
    if (depth == camLoc.size())
    {
        int cost = calc(depth - 1);
        if (cost < min_blind)
        {
            min_blind = cost;
        }
        return;
    }
    int type = camType[depth];
    for (int c = 0; c < choices[type]; c++)
    {
        // 카메라의 종류에 따라 가능한 경우의 수를 하나 골라서 저장하고 다음 단계로 넘어감
        camStatus[depth] = c;
        dfs(depth + 1);
    }
}

int main()
{
    cin >> N >> M; // height, width

    map = vector<vector<int>>(N, vector<int>(M));

    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            int t;
            cin >> t;
            map[n][m] = t;
            if (0 < t && t < 6)
            {
                camLoc.push_back(make_pair(n, m));
                camType.push_back(t);
            }
        }
    }

    dfs(0);

    cout << min_blind;

    return 0;
}