17136. 색종이 붙이기

문제링크 : https://www.acmicpc.net/problem/17136

---

#include <iostream>
 
using namespace std;
 
int arr[10][10];
bool visited[10][10];
int result = 25;
bool finishFlag = false;
int min(int a, int b) {
    if (a > b) return b;
    else return a;
}
int check(int a, int b) {
    for (int t = 5; t >= 1; t--) {
        if (a + t > 10 || b + t > 10) continue;
        bool flag = true;
        for (int i = a; i < a + t; i++) {
            for (int j = b; j < b + t; j++) {
                if (arr[i][j] == 0||visited[i][j]) {
                    flag = false;
                    i = a + t;
                    break;
                }
            }
        }
        if (flag) {
            return t;
        }
    }
    return 0;
}
void dfs(int x,int y,int count[]) {
    if (x == 10) {
        dfs(0, y + 1, count);
        return;
    }
    if (x == 9 && y == 9) {
        if (!visited[x][y] && arr[x][y] == 1) {
            if (count[1] >= 5) return;
            count[1]++;
        }
        int sum = count[1] + count[2] + count[3] + count[4] + count[5];
        result = min(result, sum);
        finishFlag = true;
        return;
    }
    if (visited[x][y]) {
        dfs(x + 1, y, count);
        return;
    }
    int next = check(x, y);
    if (next == 0) {
        visited[x][y] = true;
        dfs(x + 1, y, count);
        visited[x][y] = false;
        return;
    }
    
    for (int i = next; i >= 1; i--) {
        if (count[i] >= 5) continue;
        for (int iNext = 0; iNext < i; iNext++) {
            for (int jNext = 0; jNext < i; jNext++) {
                int nextX = x + iNext;
                int nextY = y + jNext;
                visited[nextX][nextY] = true;
            }
        }
        count[i]++;
        dfs(x + 1, y, count);
        count[i]--;
        for (int iNext = 0; iNext < i; iNext++) {
            for (int jNext = 0; jNext < i; jNext++) {
                int nextX = x + iNext;
                int nextY = y + jNext;
                visited[nextX][nextY] = false;
            }
        }
    }
}
int main()
{
    fill(&arr[0][0], &arr[9][10], 0);
    fill(&visited[0][0], &visited[9][10], false);
    int count[6] = { 0 };
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dfs(0, 0, count);
    if (finishFlag) printf("%d", result);
    else printf("-1");
}