[BOJ] 18808 스티커 붙이기

문제: https://www.acmicpc.net/problem/18808

 

함수 설명:

- bool check(int x, int y): 현재 위치에 스티커를 붙일 수 있는지 판단

- void plusmap(int x, int y): 현재 위치에 스티커 붙임

- bool paste(): 붙일 수 있는 곳 찾아서 붙이기, 붙였는지 결과 리턴 -> check, plusmap 함수 사용

- void rotation(): 스티커 90도 회전시키기

 

소스코드:

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int preshape[11][11],curshape[11][11],n,m,k,realmap[41][41],res;
int xlen, ylen;
//현재 위치에 스티커를 붙일 수 있는지 판단
bool check(int x, int y) {
	for (int i = 0; i < xlen; i++) {
		for (int j = 0; j < ylen; j++) {
			if (curshape[i][j] + realmap[x + i][y + j] == 2) return false;
		}
	}
	return true;
}
//현재 위치에 스티커 붙임
void plusmap(int x, int y) {
	for (int i = 0; i < xlen; i++) {
		for (int j = 0; j < ylen; j++) {
			if (curshape[i][j] == 1) res++;
			realmap[x + i][y + j] += curshape[i][j];
		}
	}
}
//붙일 수 있는 곳 찾아서 붙이기, 붙였는지 결과 리턴
bool paste() {

	for (int i = 0; i <= n - xlen; i++) {
		for (int j = 0; j <= m - ylen; j++) {
			if (check(i, j)) {
				plusmap(i, j);
				return true;
			}
		}
	}
	return false;
}
// 스티커 90도 회전시키기
void rotation() {
	for (int i = 0; i < xlen; i++) {
		for (int j = 0; j < ylen; j++) {
			preshape[i][j] = curshape[i][j];
		}
	}
	for (int i = 0; i < xlen; i++) {
		for (int j = 0; j < ylen; j++) {
			curshape[j][xlen - 1 - i] = preshape[i][j];
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> n >> m>>k;

	for (int s = 0; s < k; s++) {
		//int a, b;
		cin >> xlen >> ylen;
		for (int i = 0; i < xlen; i++) {
			for (int j = 0; j < ylen; j++) {
				cin >> curshape[i][j];
			}
		}
		if (!paste()){
			for (int i = 0; i < 3; i++) {
				rotation();
				swap(xlen, ylen);
				if (paste()) {
					break;
				}
			}
		}
	}

	cout << res << '\n';
	return 0;
}