백준 6196, Dynamic Programming
USACO November 2006 Contest gold 2번 문제.
1014번 문제와 거의 비슷한 비트 dp 문제다.
비트 dp 만 알고 있으면 간단하게 풀 수 있다.
두 자리가 인접하거나, 주어진 board 와 해당 상태 비트가 맞지 않는 경우만 잘 제외하면 된다.
Source Code
//BOJ6196
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Mod 100000000
int N, M;
int board[20][20];
int cache[15][1 << 15];
int dp(int row, int state) {
int& ret = cache[row][state];
if (ret != -1) return ret;
ret = 0;
if (row == N - 1) {
ret = 1;
return ret;
}
int statebit[20], tstate = state;
for (int i = 0; i < 15; ++i) {
statebit[i] = tstate % 2;
tstate /= 2;
}
for (int i = 0; i < (1 << M); ++i) {
int nextstate[20], tmp = i;
for (int j = 0; j < 15; ++j) {
nextstate[j] = tmp % 2;
tmp /= 2;
}
bool chk = true;
for (int j = 0; j < M; ++j) {
if (nextstate[j] && nextstate[j + 1]) chk = false;
// 두 자리가 횡으로 인접한 경우
if (nextstate[j] && statebit[j]) chk = false;
// 두 자리가 종으로 인접한 경우
if (nextstate[j] && board[row+1][j] == 0) chk = false;
// 비트의 상태와 보드의 상태가 맞지 않는 경우.
if (!chk) break;
}
if (!chk) continue;
ret += dp(row + 1, i);
ret %= Mod;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> board[i][j];
}
}
memset(cache, -1, sizeof(cache));
int ans = 0;
for (int i = 0; i < (1 << M); ++i) {
//memset(cache, -1, sizeof(cache));
int nextstate[20];
int tmp = i;
for (int j = 0; j < 15; ++j) {
nextstate[j] = tmp % 2;
tmp /= 2;
}
bool chk = true;
for (int j = 0; j < 15; ++j) {
if (nextstate[j] && nextstate[j + 1]) chk = false;
if (nextstate[j] && board[0][j] == 0) chk = false;
if (!chk) break;
}
if (!chk) continue;
ans += dp(0, i);
ans %= Mod;
}
printf("%d\n", ans);
return 0;
}