[백준 18808] 스티커 붙이기

분류 

시뮬레이션

요구사항

문제에 주어진 대로 스티커를 놓을 수 있나, 없나 판단한다.

스티커를 놓을 수 있다면 붙인다.

최대 몇칸을 채울 수 있는가 출력한다.

 

풀이

1. 위치 정하기

- 모든 그래프의 정점에서 현재 모양의 스티커를 놓을 수 있는지 확인한다.

2. 안될 경우 회전하기

- 안될 경우 회전 시킨다

- 노트에다가 현재 스티커 모양과 회전 시킨 후 스티커 모양을 좌표로 그린 후, 구현한다.

- 1~2개만 그려보면 구현할 수 있다.

- temp[i][j]= map[c-j+1][i]

3. 정답 출력

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;
struct go {
	int r;
	int c;
	int Nmap[11][11];
};
int n, m, k;
int map[44][44];
go pos[101];
void rotate(int num) {
	int temp[11][11];
	int temp1 = pos[num].r;
	pos[num].r = pos[num].c;
	pos[num].c = temp1;
	//cout << "R" << r << "C" << c << endl;
	for (int i = 0; i < pos[num].r; i++) {
		for (int j = 0; j < pos[num].c; j++) {
			temp[i][j] = pos[num].Nmap[pos[num].c-1 - j][i];
		}
	}
	for (int i = 0; i < pos[num].r; i++) {
		for (int j = 0; j < pos[num].c; j++) {
			pos[num].Nmap[i][j] = temp[i][j];
		}
	}

}
bool check(int r, int c,int num) {
	if (r + pos[num].r > n) {
		return false;
	}
	if (c + pos[num].c > m) {
		return false;
	}
	for (int i = r, ii = 0; i < r + pos[num].r; i++, ii++) {
		for (int j = c, jj = 0; j < c + pos[num].c; j++, jj++) {
			if (pos[num].Nmap[ii][jj] == 1) {
				if (map[i][j] != 0) return false;
			}
		}
	}
	return true;
}
void draw(int r, int c, int num) {
	for (int i = r , ii = 0 ; i < r + pos[num].r; i++, ii++) {
		for (int j = c, jj = 0 ; j < c + pos[num].c; j++, jj++) {
			if (pos[num].Nmap[ii][jj] == 1) {
				map[i][j] = 1;
			}
		}
	}
}
void solve(int num) {
	for (int z = 0; z < 4; z++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (check(i, j, num)) {
					draw(i, j, num);
					return;
				}
			}
		}
		rotate(num);
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &pos[i].r, &pos[i].c);
		for (int j = 0; j < pos[i].r; j++) {
			for (int k = 0; k < pos[i].c; k++) {
				scanf("%d", &pos[i].Nmap[j][k]);
			}
		}
	}
	for (int i = 0; i < k; i++) {
		solve(i);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}