8000 Merge pull request #469 from CLOUDoort/master · dkim-coder/basic-algo-lecture@06c4a65 · GitHub
[go: up one dir, main page]

Skip to content

Commit 06c4a65

Browse files
Merge pull request encrypted-def#469 from CLOUDoort/master
Create 14502_2.cpp
2 parents a1eeadb + cefa9de commit 06c4a65

File tree

1 file changed

+80
-0
lines changed

1 file changed

+0
lines changed

0x0D/solutions/14502_2.cpp

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
// Authored by : qwee158
2+
// Co-authored by : -
3+
// http://boj.kr/f2d4f1d210bb47d2a523091250318464
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
#define X first
7+
#define Y second
8+
9+
int n, m;
10+
int board[10][10];
11+
int play_board[10][10];
12+
int vis[10][10];
13+
int dx[4] = {1, 0, -1, 0};
14+
int dy[4] = {0, 1, 0, -1};
15+
queue<pair<int, int>> v;
16+
vector<pair<int, int>> blank;
17+
18+
bool oob(int x, int y) {
19+
return x < 0 || x >= n || y < 0 || y >= m;
20+
}
21+
void reset_board() {
22+
for(int i = 0; i < n; i++) {
23+
fill(vis[i], vis[i]+m, 0);
24+
for(int j = 0; j < m; j++) {
25+
play_board[i][j] = board[i][j];
26+
if(board[i][j] == 2) {
27+
v.push({i, j});
28+
vis[i][j] = 1;
29+
}
30+
}
31+
}
32+
}
33+
34+
int bfs() {
35+
while(!v.empty()) {
36+
int x, y; tie(x, y) = v.front(); v.pop();
37+
for(int dir = 0; dir < 4; dir++) {
38+
int nx = x + dx[dir];
39+
int ny = y + dy[dir];
40+
if(oob(nx, ny)) continue;
41+
if(vis[nx][ny] || play_board[nx][ny] != 0) continue;
42+
play_board[nx][ny] = 2;
43+
vis[nx][ny] = 1;
44+
v.push({nx, ny});
45+
}
46+
}
47+
int sum = 0;
48+
for(int i = 0; i < n; i++) {
49+
for(int j = 0; j < m; j++) {
50+
if(play_board[i][j] == 0) sum++;
51+
}
52+
}
53+
return sum;
54+
}
55+
56+
int main(void) {
57+
ios::sync_with_stdio(0);
58+
cin.tie(0);
59+
cin >> n >> m;
60+
for(int i = 0; i < n; i++) {
61+
for(int j = 0; j < m; j++) {
62+
cin >> board[i][j];
63+
if(board[i][j] == 0) blank.push_back({i, j});
64+
}
65+
}
66+
vector<int> brute(blank.size(), 1);
67+
fill(brute.begin(), brute.end()-3, 0);
68+
int mx = 0;
69+
do {
70+
reset_board();
71+
// 빈 칸 중에 3개를 선택해서 벽으로 만들기
72+
for(int i = 0; i < brute.size(); i++) {
73+
if(brute[i] == 1) {
74+
play_board[blank[i].X][blank[i].Y] = 1;
75+
}
76+
}
77+
mx = max(mx, bfs());
78+
} while(next_permutation(brute.begin(), brute.end()));
79+
cout << mx;
80+
}

0 commit comments

Comments
 (0)
0