14391번 종이 조각

www.acmicpc.net/problem/14391

14391번: 종이 조각

 

use 2차원 배열이 true일 때는 가로, false일 때는 세로로 생각하여 계산한다.

 

 

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 5

int R, C, answer = INT32_MIN;
int p[MAX][MAX];
bool use[MAX][MAX], tmp[MAX][MAX];

int calc(vector<int> &v)
{
    string str = "";
    for (auto i : v) str += to_string(i);
    return stoi(str);
}

vector<int> make_set(int r, int c, int L, bool pivot)
{
    vector<int> v;
    // 가로 == true
    if (pivot) for (int j = c; j < c + L; j++) v.push_back(p[r][j]);  
    // 세로 == false
    else for (int i = r; i < r + L; i++) v.push_back(p[i][c]); 
    return v;
}

int len(int r, int c, bool pivot)
{
    int ret = 0;

    // 가로 == true
    if (pivot) {
        for (int j = c; j < C; j++) {
            if (use[r][j] && !tmp[r][j]) {
                tmp[r][j] = true;
                ++ret;
            }
            else break;          
        }
    }
    // 세로 == false
    else {
        for (int i = r; i < R; i++) {
            if (!use[i][c] && !tmp[i][c]) {
                tmp[i][c] = true;
                ++ret;
            }
            else break;         
         }
    }

    return ret;
}

void bf(int y, int x)
{
    if (y == R) {
        memset(tmp, false, sizeof(tmp));

        int sum = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (p[i][j] && !tmp[i][j]) {
                    int L = len(i, j, use[i][j]);
                    vector<int> v = make_set(i, j, L, use[i][j]);
                    sum += calc(v);
                }
            }
        }

        answer = max(answer, sum);

        return;
    }

    if (x == C) {
        ++y;
        x = 0;
    }

    use[y][x] = true;
    bf(y, x + 1);

    use[y][x] = false;
    bf(y, x + 1);
}

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

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

    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) scanf("%1d", &p[i][j]);
 
    bf(0, 0);

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

    return 0;
}