[C++] 백준 문제풀이 (Simulation) 18808번 스티커 붙이기

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

18808번: 스티커 붙이기

 

 

 

 

 

#include <bits/stdc++.h>


int n, m, k;
int r[100][4]; // r[i][0] i번째 기본스티커, 180도 회전 행  r[i][1] i 번째 스티커 90도, 270도 행
int c[100][4]; // c[i][0] i번째 기본스티커, 180도 회전 열  c[i][1] i 번째 스티커 90도, 270도 열
int stickers[100][4][10][10];
int note[40][40];
int backup[40][40];
int ans;


void rotate(int type, int version){
	int len_y = r[type][version];
	int len_x = c[type][version];
	for (int y = 0; y < len_y; ++y){
		for (int x = 0; x < len_x; ++x){
			stickers[type][version + 1][x][len_y - 1 - y] = stickers[type][version][y][x];
		}
	}
}


void copy(int from[40][40], int to[40][40]) {
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			to[i][j] = from[i][j];
		}
	}
}

bool fill(int type, int version, int b, int a, int len_y, int len_x) {
	for (int y = 0; y < len_y; ++y){
		for (int x = 0; x < len_x; ++x){
			if (stickers[type][version][y][x] == 0) continue;
			if (note[b + y][a + x] == 1 || b + y  >= n || a + x >= m) {
				copy(backup, note);
				return false;
			}
			note[b + y][a + x] = 1;
		}
	}
	copy(note, backup);
	return true;
}


bool check(int type, int version) {

	int len_y = r[type][version];
	int len_x = c[type][version];

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			bool is_good = fill(type, version, i, j, len_y, len_x);
			if (is_good) return true;
		}
	}
	return false;
}



int main(int argc, char** argv){

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m >> k;


	for (int i = 0; i < k; ++i){
		std::cin >> r[i][0]  >> c[i][0];
		r[i][3] = r[i][1] = c[i][2] = c[i][0];
		c[i][3] = c[i][1] = r[i][2] = r[i][0];
		for (int y = 0; y < r[i][0]; ++y){
			for (int x = 0; x < c[i][0]; ++x){
				std::cin >> stickers[i][0][y][x];
			}
		}
	}


	for (int type = 0; type < k; ++type){
		for (int version = 0; version < 3; ++version){
			rotate(type, version);
		}
	}

	copy(note, backup);

	for (int type = 0; type < k; ++type){
		for (int version = 0; version < 4; ++version){
			bool is_good = check(type, version);
			if (is_good) break;
		}
	}

	for (int y = 0; y < n; ++y){
		for (int x = 0; x < m; ++x){
			if (note[y][x] == 1) ++ans;
		}
	}


	std::cout << ans << "\n";
	return 0;
}