십자가 2개 놓기 17085

문제

접근 방법

십자가를 놓을 수 있는지 확인하고 놓을 수 있으면 놓고 다음 십자가 위치를 찾으면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> pos;
vector<vector<bool>> map;
int N, M, ret = 0;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

bool canCross(int y, int x, int len)
{
    for (int i = len; i >= 0; --i)
    {
        for (int j = 0; j < 4; ++j)
        {
            int ny = y + dy[j] * i, nx = x + dx[j] * i;
            if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx])
                return false;
        }
    }
    return true;
}
void buildCross(int y, int x, int len, bool isBuild)
{
    for (int i = len; i >= 0; --i)
    {
        for (int j = 0; j < 4; ++j)
        {
            int ny = y + dy[j] * i, nx = x + dx[j] * i;
            map[ny][nx] = isBuild;
        }
    }
}
void dfs(int idx, int depth, int multi)
{
    if (depth == 2)
    {
        ret = multi > ret ? multi : ret;
        return;
    }
    for (int i = idx; i < pos.size(); ++i)
    {
        pii p = pos[i];
        int y = p.first, x = p.second;
        for (int len = 0; len < 8; ++len)
        {
            if (!canCross(y, x, len))
                break;
            buildCross(y, x, len, true);
            dfs(i + 1, depth + 1, multi * (1 + len * 4));
            buildCross(y, x, len, false);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = vector<vector<bool>>(N, vector<bool>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            char c;
            cin >> c;
            if (c == '.')
                map[i][j] = true;
            else
                pos.push_back({i, j});
        }
    dfs(0, 0, 1);
    cout << ret;
    return 0;
}

풀이

모든 위치에서 가능성을 확인해도 시간 안에 가능하다.
즉 완전 탐색 문제이다.
십자가의 넓이는 길이*4+1이라는 것으로 계산할 수 있다.