8000 Create 14502_2.cpp · dkim-coder/basic-algo-lecture@cefa9de · GitHub
[go: up one dir, main page]

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit cefa9de

Browse files
authored
Create 14502_2.cpp
1 parent f1f4d01 commit cefa9de

File tree

1 file changed

+80
-0
lines changed

1 file changed

+80
-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