[17136번] 색종이 붙이기

17136번: 색종이 붙이기

 

www.acmicpc.net

1*1, 2*2, 3*3, 4*4, 5*5 크기의 색종이가 각각 5장 씩 주어진다.

이 색종이들 만 이용해서 주어진 공간에 완벽하게 붙이면 된다.

조건

1. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안된다.

2. 겹쳐도 안 된다.

3. 칸의 경계와 일치하게 붙여야 한다. 즉, 0이 적힌 칸에는 색종이가 있으면 안 된다.

맵의 크기가 10*10으로 작기 때문에 완전탐색으로 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
struct pnt { int r, c; };
int map[10][10];
vector<pnt>one; //맵에서 주어지는 1의 위치
int oneVisit[100];
int Paper[6] = { 0,5,5,5,5,5 };
int oneCnt;
int ans = 987654321;
 
bool rangeChk(int r, int c) {
    if (!(r < 0 || c < 0 || r >= 10 || c >= 10)) return true;
    return false;
}
 
void dfs(int dep) {
    int r = -1, c = -1;
    for (register int i = 0; i < one.size(); i++) {
        if (map[one[i].r][one[i].c] == 1) {
            r = one[i].r;
            c = one[i].c;
            break;
        }
    }
    if (r == -1 && c == -1) {
        ans = min(ans, dep);
        return;
    }
    int size = 5;
    while (size > 0) {
        if (rangeChk(r + size-1, c + size-1)) {
            break;
        }
        size--;
    }
 
    for (int s = size; s > 0; s--) {
        if (Paper[s] == 0) continue;
        bool OK = true;
        for (int rr = r; rr < r + s; rr++) {
            for (int cc = c; cc < c + s; cc++) {
                if (map[rr][cc] != 1) {
                    OK = false;
                    break;
                }
            }
        }
        if (!OK) continue;
        for (int rr = r; rr < r + s; rr++) {
            for (int cc = c; cc < c + s; cc++) {
                map[rr][cc] = -1;
            }
        }
        Paper[s]--;
        dfs(dep + 1);
        Paper[s]++;
        for (int rr = r; rr < r + s; rr++) {
            for (int cc = c; cc < c + s; cc++) {
                map[rr][cc] = 1;
            }
        }
    }
}
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int r = 0; r < 10; r++) {
        for (int c = 0; c < 10; c++) {
            cin >> map[r][c];
            if (map[r][c] == 1) one.push_back({ r,c });
        }
    }
    oneCnt = one.size();
    dfs(0);
    if (ans == 987654321) ans = -1;
    cout << ans;
    return 0;
}