[백준/BOJ] 17085 십자가 2개 놓기

문제 : 17085 십자가 2개 놓기

17085번: 십자가 2개 놓기

N, M의 크기가 15밖에 안되므로 단순한 구현 문제이다.

모든 칸에 대해서 십자가 크기별로 넣어봐야 하는데

총 2개의 십자가를 배치해야 하므로 재귀 함수를 이용하면

코드의 길이를 단축해서 짤 수 있다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, ans;
ll dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string arr[20];
ll f(ll x, ll y, ll depth){
    ll ret=0;
    for (int i=0;i<=7;i++){ // 십자가 변의 길이
        ll chk=1;
        for (int j=-i;j<=i;j++){ // 배치 가능한지 확인
            if (x+j<0 || x+j>=N || y+j<0 || y+j>=M || arr[x+j][y]!='#' || arr[x][y+j]!='#')
                chk=0;
        }
        if (chk){ 
            for (int j=-i;j<=i;j++){
                arr[x+j][y]='.';
                arr[x][y+j]='.';
            }
            if (depth) // 두번째 십자가라면 즉시 반환
                ret=i*4+1;
            else{ // 첫번째 십자가라면 한번더 탐색
                for (int j=0;j<N;j++){
                    for (int k=0;k<M;k++)
                        ret=max(ret,(i*4+1)*f(j,k,1));
                }
            }
            for (int j=-i;j<=i;j++){
                arr[x+j][y]='#';
                arr[x][y+j]='#';
            }
        }
        else
            break;
    }
    return ret;
}
int main(){
    cin >> N >> M;
    for (int i=0;i<N;i++)
        cin >> arr[i];
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++)
            ans=max(ans,f(i,j,0));
    }
    cout << ans;
    return 0;
}