UVa11725 - Colorful Board(BITMASK+DP)
You are given a board. You are asked to draw M horizontal lines and N vertical lines in that board, so that the whole board is divided into (M+1) x (N+1) cells. So there will be M + 1 rows each of which will exactly contain N + 1 cells.
Now you are asked to color every cell. For these purpose, you are given four colors.
Red
Green
Blue
Orange
To make the board more beautiful and colorful, you have to be careful, so that no two adjacent cells contain the same color. Two cells are considered adjacent if they share a common side.
You are also given some forbidden cells. You must not draw anything in those cells. But you must color every other cell which are not forbidden using a single color.
You have to answer in how many ways you can color this board.
Red
Green
Blue
Orange
Valid
Green
Orange
Orange
Green
Valid
Orange
Green
Orange
Blue
Invalid
Figure: Some examples of valid and invalid coloring, where M = 1, N = 1 and no forbidden cell.
Input
Input will start with an integer T(T<=50) which indicates the number of test case. Each case will start with two integers M and N (0<=M, N<=6), number of horizontal lines and number of vertical lines. Next line will contain an integer K ( 0<=K<=(M+1)*(N+1) ), which indicates the number of forbidden cells. Each of the next K lines will contain two integers x and y (1<=x<=M+1, 1<=y<=N+1), representing one forbidden cell, which is yth cell of xth row. Each given forbidden cells are distinct.
Output
For each test case, output a single line in the form “Case #: P”, where # will be replaced by the case number and P will be replaced by the number of valid ways you can draw the given board. The result can be very large you should output the result modulo 1000000007.
Sample Input Output for Sample Input
2 1 1 1 2 1 0 0 0
Case 1: 36 Case 2: 4 #include
#include
#include
using namespace std;
typedef long long ll;
ll dp[7][16384];
ll no[7][7];
const int MOD = 1000000007;
int fmask;
int n,m;
void init(){
memset(dp,0,sizeof dp);
memset(no,0,sizeof no);
fmask = 1<>col*2)&3,left = (nowmask>>(col-1)*2)&3;
for(int i = 0; i < 4; i++){
if((col==0||no[row][col-1]||i!=left)&&(row==0||no[row-1][col]||i!=up)){
nowmask |= i<> ncase;
while(ncase--){
cin >> n >> m >> k;
m++;
n++;
init();
while(k--){
int a,b;
cin >> a >> b;
a--;b--;
no[a][b] = 1;
}
dfs(0,0,0,0,1);
for(int i = 1; i < n; i++){
for(int j = 0; j < fmask; j++){
if(dp[i-1][j]){
dfs(i,0,j,0,dp[i-1][j]);
}
}
}
ll ans = 0;
for(int i = 0; i < fmask; i++)
ans = (ans+dp[n-1][i])%MOD;
printf("Case %d: %lld
",T++,ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)
python 풀이
DP를 이용해 풀이
보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서
고민을 했는데
이 문구 덕분에 DP 를 이용해 풀이할 수 있었다
뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다
코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#include
#include
using namespace std;
typedef long long ll;
ll dp[7][16384];
ll no[7][7];
const int MOD = 1000000007;
int fmask;
int n,m;
void init(){
memset(dp,0,sizeof dp);
memset(no,0,sizeof no);
fmask = 1<>col*2)&3,left = (nowmask>>(col-1)*2)&3;
for(int i = 0; i < 4; i++){
if((col==0||no[row][col-1]||i!=left)&&(row==0||no[row-1][col]||i!=up)){
nowmask |= i<> ncase;
while(ncase--){
cin >> n >> m >> k;
m++;
n++;
init();
while(k--){
int a,b;
cin >> a >> b;
a--;b--;
no[a][b] = 1;
}
dfs(0,0,0,0,1);
for(int i = 1; i < n; i++){
for(int j = 0; j < fmask; j++){
if(dp[i-1][j]){
dfs(i,0,j,0,dp[i-1][j]);
}
}
}
ll ans = 0;
for(int i = 0; i < fmask; i++)
ans = (ans+dp[n-1][i])%MOD;
printf("Case %d: %lld
",T++,ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.