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