HDU 4012 Paint on a Wall
【摘要】 题目链接~~>
做题感悟：这题只能说很“ 经典 ” 。
解题思路：题意就是给你一个二行Ｎ例的一面墙，在墙上涂颜色，问你最少粉刷多少次，能达到给你的目标墙的状态，（每次粉刷只能粉刷出一个矩形，矩形可以是一行Ｎ例，也可以是二行Ｎ例）；
思想：广度优先搜索（因为找最短路）
状态表示：
状态用二制位表示。例如当Ｎ＝４时，就用8位二进制数表示...
做题感悟：这题只能说很“ 经典 ” 。
解题思路：题意就是给你一个二行Ｎ例的一面墙，在墙上涂颜色，问你最少粉刷多少次，能达到给你的目标墙的状态，（每次粉刷只能粉刷出一个矩形，矩形可以是一行Ｎ例，也可以是二行Ｎ例）；
思想：广度优先搜索（因为找最短路）
状态表示：
状态用二制位表示。例如当Ｎ＝４时，就用8位二进制数表示状态如：
1100
1010
‘‘０’’表示与目标状态颜色不一致，‘１’表示一致。
初始状态当然为：
0000
0000
因为和目标状态没有相同颜色。
目标状态自然为：
1111
1111
状态转移：
状态转移就是粉刷墙的过程，按传统套路很容易把粉刷的颜色也考虑进去。这样就走弯路了。
仔细想想会发现 每次粉刷，都会使一状态中的一些０变成１。从而越来越接近目标状态。
问题来了，每次粉刷多大？粉刷的大小受什么影响？
先分两种情况：
第一种是刷一行，在图上选一个点的颜色粉刷，分别向该点的左右粉刷，如果遇到和选取点颜色相同，则将当前状态该位的０变成１，表示与目标状态相同 。
第二种是刷两行，刷两行只考虑一行就可以，在其中一行寻解时，同时考虑同列的另一行，也就是在列相同的情况下判断两行的颜色，以及粉刷。
这样就可以从一个状态转移到另一个状态。
注：上述方法可以得到一个极大粉刷区域， 每次状态转移全是转移最大粉刷区域，显然是不够准确的，算出最大粉刷区域后应该也将该区域的子集加到扩展队列中。求一个状态的子集的方法：整数temp的位数为当前状态 ，那么for(int j=temp;j;j=temp&(j-1))；j就为子状态。可以自己模拟体会一下。
判重：
根据状态抽象，最多有２<１６种状态，可以开一个bool型数组flag[1<<16]；如flag[i]＝１,则表示i二进制位表示的这个状态以经出现过。
代码：
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
#define LEN sizeof(struct node)
-
#define pret(a,b) memset(a,b,sizeof(a))
-
#define lld __int64
-
const double PI = 3.1415926 ;
-
const double INF = 999999999 ;
-
const double esp = 1e-4 ;
-
const lld md= 2810778 ;
-
const int MX = 20 ;
-
int n ;
-
char s[MX] ;
-
bool vis[1<<16] ;
-
struct node
-
{
-
int key,step ; // key 表状态 step 记录步数
-
} ;
-
int bfs()
-
{
-
queue<node>q ;
-
node curt,next ;
-
while(!q.empty()) q.pop() ;
-
memset(vis,false,sizeof(vis)) ;
-
curt.key=curt.step=0 ;
-
vis[0]=true ;
-
q.push(curt) ;
-
while(!q.empty())
-
{
-
curt=q.front() ;
-
q.pop() ;
-
for(int i=0 ;i<(n<<1) ;i++) // 遍历每一个点
-
{
-
int key=curt.key,ky=0 ;
-
next.step=curt.step+1 ; // 步数加一
-
if(key&(1<<i)) continue ;
-
// 先单行左右扩展
-
for(int j=i ;j<(i/n+1)*n ;j++)// 从当前节点向右扩展
-
{
-
if(key&(1<<j)) break ;// 遇到已经染色的就结束
-
if(s[i]==s[j]) ky=ky|(1<<j) ; // 与起始颜色一样 ~> 染色
-
}
-
for(int j=i-1 ;j>=(i/n)*n ;j--) // 从当前节点向左扩展
-
{
-
if(key&(1<<j)) break ;
-
if(s[i]==s[j]) ky=ky|(1<<j) ;
-
}
-
if((key|ky)==(1<<(n*2))-1) return next.step ; // 放在这可以减少时间
-
for(int j=ky ;j ;j=key&(j-1))
-
{
-
if(!vis[key|j])
-
{
-
vis[key|j]=true ;
-
next.key=key|j ;
-
q.push(next) ;
-
}
-
}
-
// 以上为单行双向扩展
-
if(i/n) continue ;
-
key=curt.key ; ky=0 ;
-
if(key&(1<<(i+n))) continue ;
-
for(int j=i ;j<n ;j++)
-
{
-
if((key&(1<<j))||(key&(1<<(j+n)))) break ;
-
if(s[i]==s[j]) ky=ky|(1<<j) ;
-
if(s[i]==s[j+n])ky=ky|(1<<(j+n)) ;
-
}
-
for(int j=i-1 ;j>=0 ;j--)
-
{
-
if((key&(1<<j))||(key&(1<<(j+n)))) break ;
-
if(s[i]==s[j]) ky=ky|(1<<j) ;
-
if(s[i]==s[j+n]) ky=ky|(1<<(j+n)) ;
-
}
-
if((key|ky)==(1<<(n*2))-1) return next.step ;
-
for(int j=ky ;j ;j=ky&(j-1)) // 切记要枚举子集：因为并不一定需要涂最大区域，如果涂了最大区域
-
{ //别的地方就没法连续涂了。
-
if(!vis[key|j])
-
{
-
vis[key|j]=true ;
-
next.key=key|j ;
-
q.push(next) ;
-
}
-
}
-
}
-
}
-
return 0 ;
-
}
-
int main()
-
{
-
int Tx,q=1 ;
-
scanf("%d",&Tx) ;
-
while(Tx--)
-
{
-
scanf("%d",&n) ;
-
scanf("%s",s) ; // 用一维存储
-
scanf("%s",s+n) ;
-
printf("Case #%d: %d\n",q++,bfs()) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/23338569
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）