문제 출처: https://www.algospot.com/judge/problem/read/BOARDCOVER
algospot.com :: BOARDCOVER
게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 입력 력의 첫
www.algospot.com
게임판을 채우는 문제입니다. 정사각형 모양의 흰 칸 3개로 L자 모양을 만들어서 게임판을 채우는 문제입니다. 재귀를 통해서 게임판을 직접 채워보는 방식으로 문제를 풀었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#include<iostream>
#include<string>
using namespace std;
char map[20][20];
int T, H, W;
int ans = 0;
bool InRange(int y, int x)
{
return 0 <= x && x < W && 0 <= y && y < H;
}
bool cover(int y, int x, int type, char block)
{
int nx, ny, nx1, ny1;
if (type == 1)
{
nx = x;
ny = y + 1;
nx1 = x + 1;
ny1 = y + 1;
}
else if (type == 2)
{
nx = x;
ny = y + 1;
nx1 = x - 1;
ny1 = y + 1;
}
else if (type == 3)
{
nx = x + 1;
ny = y;
nx1 = x;
ny1 = y + 1;
}
else
{
nx = x + 1;
ny = y;
nx1 = x + 1;
ny1 = y + 1;
}
if (InRange(ny, nx) && InRange(ny1, nx1) && map[ny][nx] != block && map[ny1][nx1] != block)
{
map[y][x] = block;
map[ny][nx] = block;
map[ny1][nx1] = block;
return true;
}
return false;
}
void back()
{
int x, y;
x = y = -1;
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
if (map[i][j] == '.')
{
x = j;
y = i;
break;
}
}
if (y != -1) break;
}
if (y == -1)
{
ans++;
return;
}
for (int i = 1; i < 5; i++)
{
//bool check = cover(y, x, i, 'L');
if (cover(y,x,i,'#'))
{
back();
cover(y, x, i, '.');
}
}
}
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> T;
for (int t = 1; t <= T; t++)
{
cin >> H >> W;
ans = 0;
int v = 0;
for (int i = 0; i < H; i++)
{
string str;
cin >> str;
for (int j = 0; j < W; j++)
{
map[i][j] = str[j];
if (str[j] == '.')
v++;
}
}
if (v % 3 != 0)
{
cout << 0 << '\n';
continue;
}
back();
cout << ans << '\n';
}
}
|
먼저, 제가 짠 코드입니다. 아직 초보라 너무 지저분하네요 ㅠㅠ 빈칸의 개수가 3의 배수가 아니면 절대로 L자 블록으로 채울 수 없므로 0을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include<iostream>
#include<string>
using namespace std;
int map[20][20];
int coverType[4][3][2] = {
{ {0,0}, { 1 , 0 }, { 0 , 1 } },
{ {0,0},{ 0 , 1 }, { 1 , 1 } },
{ {0,0},{ 1 , 0 }, { 1 , 1 } },
{ {0,0},{ 1 , 0 }, { 1 , -1 } },
};
int T, H, W;
int ans = 0;
bool InRange(int y, int x)
{
return 0 <= x && x < W && 0 <= y && y < H;
}
bool cover(int y, int x, int type, int block)
{
bool check = true;
for (int i = 0; i < 3; i++)
{
int ny = y + coverType[type][i][0];
int nx = x + coverType[type][i][1];
if (!InRange(ny, nx))
check = false;
else if ((map[ny][nx] += block) > 1)
check = false;
}
return check;
}
void back()
{
int x = -1, y = -1;
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
if (map[i][j] == 0)
{
x = j;
y = i;
break;
}
}
if (y != -1) break;
}
if (y == -1)
{
ans++;
return;
}
for (int i = 0; i < 4; i++)
{
if (cover(y,x,i,1))
{
back();
}
cover(y, x, i, -1);
}
}
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> T;
for (int t = 1; t <= T; t++)
{
cin >> H >> W;
ans = 0;
int v = 0;
for (int i = 0; i < H; i++)
{
string str;
cin >> str;
for (int j = 0; j < W; j++)
{
if (str[j] == '#')
map[i][j] = 1;
else
map[i][j] = 0;
}
}
if (v % 3 != 0)
{
cout << 0 << '\n';
continue;
}
back();
cout << ans << '\n';
}
}
|
책에 있는 코드를 참고하여 짠 코드입니다. 전체적으로 비슷하지만 type에 따라 블록의 영역을 3차원 배열을 이용하여 짯습니다. 제가 짠 코드는 L자 블록을 채울때 3칸이 범위를 넘어가지 않고 빈 칸일때만 채우고 빼지만 책을 참고한 코드는 일단 조건에 상관없이 채우고 뺍니다. 전체적으로 참고한 코드가 훨씬 가독성이 좋고 깔금한 것 같습니다. 특히 블록을 채우고 빼는 과정이 재미있었습니다. 채울때는 1을 더해주고 빼는 과정은 -1을 더해줍니다.