HDU 4012 Paint on a Wall(状压+bfs)
2024-10-07 13:36:22
Paint on a Wall
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 830 Accepted Submission(s): 325
Problem Description
Annie
wants to paint her wall to an expected pattern. The wall can be
represented as a 2*n grid and each grid will be painted only one color.
Annie has a brush which could paint a rectangular area of the wall at a
single step. The paint could be overlap and the newly painted color will
replace the older one.
For a given pattern of the wall, your task
is to help Annie find out the minimum possible number of painting steps.
You can assume that the wall remains unpainted until Annie paint some
colors on it.
wants to paint her wall to an expected pattern. The wall can be
represented as a 2*n grid and each grid will be painted only one color.
Annie has a brush which could paint a rectangular area of the wall at a
single step. The paint could be overlap and the newly painted color will
replace the older one.
For a given pattern of the wall, your task
is to help Annie find out the minimum possible number of painting steps.
You can assume that the wall remains unpainted until Annie paint some
colors on it.
Input
There are multiple test cases in the input. The first line contains the number of test cases.
For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)
Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.
See the sample input for further details.
For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)
Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.
See the sample input for further details.
Output
For each test case, output only one integer denoting the minimum number of steps.
Sample Input
3
3
ABA
CBC
3
BAA
CCB
3
BBB
BAB
Sample Output
Case #1: 3
Case #2: 3
Case #3: 2
n <= 8 。。很经典的搜索。。
状压 + bfs , 用二进制表示是否到达目标颜色。
可以发现一个性质就是 没发现一个未达到目标颜色的点可以直接以它作为顶点向左,向右构造新的状态
写得比较烂, 跑了将近 3 s
#include <bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define X first
#define Y second
const int N = <<;
int n ;
string s , s2 ;
struct node {
int w , st ;
node(){}
node( int w , int st ):w(w),st(st){}
bool operator < ( const node &a ) const {
return w > a.w ;
}
}; void update( int &st , int i , int j , bool tag ) {
if( ( st & ( <<j ) ) && s[j] != s[i] ) st ^= (<<j) ;
if( !( st & ( <<j ) ) && s[j] == s[i] ) st |= (<<j) ;
if( !tag ) return ;
if( ( st & ( <<((j+n)%(*n)) ) ) && s[(j+n)%(*n)] != s[i] ) st ^= (<<((j+n)%(*n)) );
if( !( st & ( <<(j+n)%(*n)) ) && s[(j+n)%(*n)] == s[i] ) st |= (<<((j+n)%(*n)) ) ;
// cout << j << ' ' << (j+n)%(2*n) << endl ;
} void show( int st ) {
for( int i = ; i < n ; ++i ) if( st&(<<i) ) cout << '' ; else cout << '' ; cout << endl ;
for( int i = n ; i < *n ; ++i ) if( st&(<<i) ) cout << '' ; else cout << '' ; cout << endl ;
} int dis[N] , all ;
void bfs( ) {
priority_queue<node>que;
que.push( node(,) ) ;
memset( dis , 0x3f , sizeof dis );
dis[] = ;
// cout << all << endl ;
while( !que.empty() ) {
int uw = que.top().w , ust = que.top().st ;
que.pop();
if( dis[ust] < uw ) continue ;
// cout << uw << endl ; show( ust ); cout << endl ;
if( ust == all ) return ;
int vw = uw + , vst , vst2 ; for( int i = ; i < n ; ++i ) if( !( ust&(<<i)) ) {
vst = ust , vst2 = ust ;
for( int j = i ; j < n ; ++j ) { // single line
update( vst , i , j , false );
update( vst2 , i , j , true );
if( vw < dis[vst] ) {
// cout << i << ' ' << vst << endl ;
// show( vst ); cout << endl ;
dis[vst] = vw ;
que.push( node( vw , vst ) ) ;
}
if( vw < dis[vst2] ) {
// show( vst2 ); cout << endl ;
dis[vst2] = vw ;
que.push( node( vw , vst2 ));
}
}
vst = ust , vst2 = ust ;
for( int j = i ; j >= ; --j ) {
update( vst , i , j , false );
update( vst2 , i , j , true );
if( vw < dis[vst] ) {
// show( vst ); cout << endl ;
dis[vst] = vw ;
que.push( node( vw , vst ) ) ;
}
if( vw < dis[vst2] ) {
// show( vst2 ); cout << endl ;
dis[vst2] = vw ;
que.push( node( vw , vst2 ));
}
}
} for( int i = n ; i < * n ; ++i ) if( !( ust&(<<i)) ) {
vst = ust , vst2 = ust ;
for( int j = i ; j < * n ; ++j ) { // single line
update( vst , i , j , false );
update( vst2 , i , j , true );
if( vw < dis[vst] ) {
// show( vst ); cout << endl ;
dis[vst] = vw ;
que.push( node( vw , vst ) ) ;
}
if( vw < dis[vst2] ) {
// show( vst2 ); cout << endl ;
dis[vst2] = vw ;
que.push( node( vw , vst2 ));
}
}
vst = ust , vst2 = ust ;
for( int j = i ; j >= n ; --j ) {
update( vst , i , j , false );
update( vst2 , i , j , true );
if( vw < dis[vst] ) {
// show( vst ); cout << endl ;
dis[vst] = vw ;
que.push( node( vw , vst ) ) ;
}
if( vw < dis[vst2] ) {
// show( vst2 ); cout << endl ;
dis[vst2] = vw ;
que.push( node( vw , vst2 ));
}
}
}
}
} int Run() {
int _ , cas = ; cin >> _ ;
while( _-- ) {
cout << "Case #" << cas++ <<": " ;
cin >> n >> s >> s2 ;
s += s2 ;
all = (<<(n*))-;
bfs();
// cout << dis[45] << endl ;
cout << dis[all] << endl ;
}
return ;
}
int main() {
// freopen("in.txt","r",stdin);
ios::sync_with_stdio();
return Run();
}
最新文章
- Be a new gentlemen
- Redis入门指南
- zepto源码--核心方法2(class相关)--学习笔记
- Windows消息传递机制详解
- MLlib-协同过滤
- CascadeType
- 51Nod--1011最大公约数GCD
- Python 继承标准类时发生了什么
- 用Python写WebService接口并且调用
- Java中的读写锁
- linux系统管理--top命令
- 【BZOJ5502】[GXOI/GZOI2019]与或和(单调栈)
- Pro Git
- HYSBZ 4034 【树链剖分】+【线段树 】
- You Only Look Once: Unified, Real-Time Object Detection
- PAT A1136 A Delayed Palindrome (20 分)——回文,大整数
- Mac下配置多个SSH KEY访问远程Git服务
- Python中数据类型
- Node Koa2 完整教程
- Elasticsearch 实现自定义排序插件