[C] Help Caretaker
Codeforces Round #102 (Div. 1)
왼쪽 위에서부터 차례대로 놓아가는 백트래킹으로 풀 수 있다.
다음과 같은 가지치기 하나만으로도 시간 내에 답을 구할 수 있다.
현재 (i, j) 를 살펴봐야 하는 때라면
남은 칸의 수는 대략 (n*m - (i*m+j)) 칸 일 것이다.
현재까지 놓은 T의 개수를 cnt, 현재 구한 제일 좋은 답을 ans 라고 하면
cnt + (n*m - (i*m+j))/6 <= ans
라면 여기서 더 뻗어나가도 답을 갱신할 가능성이 없으므로
여기서 가지를 치면 된다.
직전 2줄의 상태를 관리하는 bitmask DP 로도 해결할 수 있다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstring> | |
| using namespace std; | |
| int n, m; | |
| char block[][3][4] = { | |
| { "###", | |
| ".#.", | |
| ".#." }, | |
| { "#..", | |
| "###", | |
| "#.." }, | |
| { ".#.", | |
| ".#.", | |
| "###" }, | |
| { "..#", | |
| "###", | |
| "..#" } | |
| }; | |
| int cell[10][10], anscell[10][10]; | |
| int bcnt, ans; | |
| bool isPlacable(int i, int j, int k) { | |
| for (int p = 0; p < 3; ++p) for (int q = 0; q < 3; ++q) { | |
| if (cell[i + p][j + q] != -1 && block[k][p][q] == '#') return false; | |
| } | |
| return true; | |
| } | |
| void setBlock(int i, int j, int k) { | |
| for (int p = 0; p < 3; ++p) for (int q = 0; q < 3; ++q) { | |
| if (block[k][p][q] == '#') cell[i + p][j + q] = bcnt; | |
| } | |
| ++bcnt; | |
| } | |
| void removeBlock(int i, int j, int k) { | |
| for (int p = 0; p < 3; ++p) for (int q = 0; q < 3; ++q) { | |
| if (block[k][p][q] == '#') cell[i + p][j + q] = -1; | |
| } | |
| --bcnt; | |
| } | |
| void go(int i, int j) { | |
| if (j >= m - 2) { | |
| go(i + 1, 0); | |
| return; | |
| } | |
| if (i == n - 2) { | |
| if (ans < bcnt) { | |
| ans = bcnt; | |
| memcpy(anscell, cell, sizeof(cell)); | |
| } | |
| return; | |
| } | |
| if (bcnt + (n * m - (i * m + j)) / 6 <= ans) { | |
| return; | |
| } | |
| for (int k = 0; k < 4; ++k) { | |
| if (isPlacable(i, j, k)) { | |
| setBlock(i, j, k); | |
| go(i, j + (k == 3 ? 3 : 2)); | |
| removeBlock(i, j, k); | |
| } | |
| } | |
| go(i, j + 1); | |
| } | |
| int main() { | |
| memset(cell, -1, sizeof(cell)); | |
| memset(anscell, -1, sizeof(anscell)); | |
| scanf("%d %d", &n, &m); | |
| if (n >= 3 && m >= 3) go(0, 0); | |
| printf("%d\n", ans); | |
| for (int i = 0; i < n; ++i) { | |
| for (int j = 0; j < m; ++j) { | |
| putchar(anscell[i][j] == -1 ? '.' : ('A' + anscell[i][j])); | |
| } | |
| putchar('\n'); | |
| } | |
| return 0; | |
| } |