https://www.acmicpc.net/problem/1941
1941번: 소문난 칠공주
총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작
www.acmicpc.net
|
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <iostream>
#include <queue>
using namespace std;
char a[7][7];
int ycnt = 0, scnt = 0;
int result = 0;
int dx[] = { 0 , 0, 1, -1 };
int dy[] = { 1, -1, 0 ,0 };
bool check[27];
int adjboard[6][6];
bool adjcheck[6][6];
bool adj()
{
int cnt = 0;
queue<pair<int, int>> q;
for (int i = 0; i < 25; i++)
{
if (check[i])
{
adjboard[i / 5][i % 5] = 1;
}
}
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if ((adjboard[i][j] == 1) && (adjcheck[i][j] == false))
{
cnt++;
if (a[i][j] == 'Y')
ycnt++;
else
scnt++;
adjcheck[i][j] = true;
q.push(make_pair(i, j));
while (!q.empty())
{
// auto cur = q.front();
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5)
{
if ((adjboard[nx][ny] == 1) && (adjcheck[nx][ny] == false))
{
adjcheck[nx][ny] = true;
if (a[nx][ny] == 'Y')
ycnt++;
else scnt++;
q.push(make_pair(nx, ny));
}
}
}
}
}
}
}
//인접해야하므로 bfs 한번에 끝나야한다!
if (cnt == 1) return true;
else return false;
}
//조합 경우의 수가 끝나고 초기화를 시켜줘야한다
void init()
{
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
adjboard[i][j] = 0;
adjcheck[i][j] = 0;
}
}
}
void comb(int idx, int cnt)
{
//7명이 찼으면 adj함수로 bfs를 하자
if (cnt == 7)
{
ycnt = scnt = 0;
if (adj())
{
if (scnt >= 4)
result++;
}
init();
return;
}
for (int i = idx; i < 25; i++)
{
if (!check[i])
{
check[i] = true;
comb(i, cnt + 1);
check[i] = false;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 5; i++)
cin >> a[i];
comb(0, 0);
cout << result << '\n';
return 0;
}
|
cs |