[BOJ] 17085. 십자가 2개 놓기

 

* 십자가를 놓을 수 있는 최대 길이를 chk[][] 에 미리 저장을 해 놓는다. 

* 십자가는 한 좌표를 중심으로 상 하 좌 우 인접한 칸으로 퍼져나간다. 

* 이 특성을 이용해서 chk에는 몇 번이나 뻗어나갔는지를 저장한다. 

* dfs(int cnt, ll res) 에는 2개의 십자가를 놓았으면 최대값을 비교하여 갱신한다. (종료조건)

 

*(0,0) ~ (n,m)까지 검사하면서 chk[][]가 1이상일 때 (== map[][] 가 # 일때) 주변을 검사하면서 십자가가 겹쳐서 생성되지 않는지 검사한다. 

*무조건 한 십자가가 크다고 정답이 되는 것은 아니기 때문에 십자가의 크기가 chk[][] 의 값보다 작더라도 dfs()를 호출해서 다른 십자가도 놓을 수 있도록 한다. (line 81)

* visited는 십자가를 놓은 자리를 표시하는데, 완벽하게 네 방향에 십자가를 놓는 경우에만 표시할 수 있도록 한다.

 

 

#include <iostream> #include <vector> #include <cstring> using namespace std; //boj 십자가 2개 놓기 <a href="https://www.acmicpc.net/problem/17085">https://www.acmicpc.net/problem/17085</a> int n, m; char map[16][16]; int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}; bool visited[16][16]; int chk[16][16]; typedef long long ll; ll ans = 0; bool checkRange(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) return false; return true; } void dfs(int cnt, ll res) { if (cnt == 2) { //최대 너비를 계산 ans = ans > res ? ans : res; return; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (chk[i][j] && !visited[i][j]) { bool c_visited[16][16]; memcpy(c_visited, visited, sizeof(visited)); int limit = chk[i][j] - 1; visited[i][j] = true; int sum = 1; if (!limit) { dfs(cnt + 1, res * sum); visited[i][j] = false; } int idx = 1; bool flag = true; while (limit-- && flag) { for (int d = 0; d < 4; d++) { int nx = i + dx[d] * idx; int ny = j + dy[d] * idx; if (checkRange(nx, ny) && !visited[nx][ny]) { } else { flag = false; break; } } if (flag) { //4방향으로 모두 알맞게 십자가를 만들었다면 for (int d = 0; d < 4; d++) { int nx = i + dx[d] * idx; int ny = j + dy[d] * idx; visited[nx][ny] = true; sum++; } dfs(cnt + 1, res * sum); idx++; } } memcpy(visited, c_visited, sizeof(visited)); } } } } int main() { ios_base::sync_with_stdio(0); <a href="http://cin.tie(0);">cin.tie(0);</a> cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == '#') { int idx = 1; bool flag = true; while (flag) { for (int d = 0; d < 4; d++) { int nx = i + dx[d] * idx; int ny = j + dy[d] * idx; if (checkRange(nx, ny) && map[nx][ny] == '#') { } else { flag = false; break; } } if (flag) { idx++; } } chk[i][j] = idx; } } } dfs(0, 1); cout << ans << '\n'; return 0; }

 

 

TC
6 12
........#...
...#....#...
...#.#######
#######.#...
##.##...#...
...#........
ans = 81

7 7
...#...
...#...
...#...
#######
...####
...#.#.
...#...
ans = 25