c++ 백준_23562_"ㄷ 만들기"

https://www.acmicpc.net/problem/23562

23562번: ㄷ 만들기

 

​

ㄷ 이 칸을 3k 씩 사용하고

n,m 의 최대가 20 이니

​

K = 1 ,2 , 3 , 4, 5, 6

까지의 경우를 브루트포스 했다.

​

#include <iostream>
#include <vector>
using namespace std;

#define INF 1000000000

int n,m,a, b;

int Dee(vector<vector<char>> page,int k,int row,int col) {


	if (row + (3 * k - 1) >= n || col + (3 * k - 1) >= m)
		return INF;

	int cost = 0;
	vector<vector<bool>> check(n, vector<bool>(m, false));

	for (int i = 0; i < 3*k; i++) {
		for (int j = 0; j < 3*k; j++) {
			

			if (k <= i && i < 2 * k) { // ㄷ 자 안쪽 부분
				if (j < k) {
					if (page[row + i][col + j] == '.') {
						cost += a;
					}
				}
				else {
					if (page[row + i][col + j] == '#') {
						cost += b;
					}
				}
			}
			else {
				if (page[row + i][col + j] == '.') { 
					cost += a;
				}
			}
			
			check[row + i][col + j] = true;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!check[i][j]) {
				if (page[i][j] == '#') {
					cost += b;
				}

			}
		}
	}

	return cost;
}


int main(void) {

	
	cin >> n >> m;
	cin >> a >> b;


	vector<vector<char>> page(n, vector<char>(m));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> page[i][j];
		}
	}

	int ans = INF;
	for (int k = 1; k <= 6; k++) {

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int cost = Dee(page, k, i, j);
				if (ans > cost) {
					ans = cost;
				}
			}
		}
	}
	cout << ans;

}