UESTC_Can You Help God Wu CDOJ 582
There is a boy named God Wu in UESTC ACM team. One day he is asked to finish a task. The task is that he has to paint a wall as the given pattern. The wall can be represented as a 2×n grid and each grid will be painted only one color. You know God Wu is a God, so he has a brush which could paint a rectangular area of the wall at a single step. As we all know, the paint could be overlap and the newly painted color will replace the older one.
God Wu is so lazy that he always want to finish something in the least steps. At first, the wall was not painted until God Wu paint some colors on it. For a given pattern of the wall, God Wu has to find out the minimum possible number of painting steps to make the wall the same as the given pattern.
Input
In the input file, the first line contains the number of test cases.
For each test case, the first contains only one integer n(1≤n≤8) indicating the length of the wall.
Then follows two lines, denoting the expected pattern of the wall. Every grid is painted by a color which is represented by a single capital letter. You can see the Input Sample for more details.
Output
For each test case, output only one integer denoting the minimum number of steps.
Sample input and output
Sample Input | Sample Output |
---|---|
3 |
Case #1: 3 |
Source
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std; char g[];
int len,all;
bool vis[];
int target;
int caculate[] = {,,,,,,,,,,,,,,,,};
typedef struct status
{
int st,step,h;
friend bool operator < (status a,status b)
{
if (a.step + a.h < b.step + b.h)
return false;
if (a.step + a.h == b.step + b.h && a.step < b.step)
return false;
return true;
} }; priority_queue<status>q; int A(status &x)
{
bool ll[];
int result = ;
memset(ll,false,sizeof(ll));
for(int i = ; i < all;++i)
if ( (!(x.st & ( << i))) && !ll[g[i]-'A'])
{
result ++;
ll[g[i]-'A'] = true;
}
return result;
} int bfs()
{
status start;
start.step = ,start.st = ;
start.h = A(start);
q.push(start);
vis[] = true;
while(!q.empty())
{
status ss = q.top();q.pop();
if (ss.st == target) return ss.step;
for(int i = ; i <len;++i)
for(int j = ;j <= len-i;++j)
{
char id;
for(int h = ;h< j;++h)
{
id = g[i+h];
int t = ss.st;
for(int v = ; v < j ;++ v)
if(g[i+v] != id)
t &= ~( << (i+v));
else
t |= ( << (i+v));
if (!vis[t])
{
status ns;
ns.step = ss.step + ;
ns.st = t;
ns.h = A(ns);
q.push(ns);
vis[t] = true;
}
} for(int h = ;h< j;++h)
{
id = g[i+h+len];
int t = ss.st;
for(int v = ; v < j ;++ v)
if(g[i+v+len] != id)
t &= ~( << (i+v+len));
else
t |= ( << (i+v+len));
if (!vis[t])
{
status ns;
ns.step = ss.step + ;
ns.h = A(ns);
ns.st = t;
q.push(ns);
vis[t] = true;
}
} for(int h = ; h < *j;++ h)
{
if (h >= j)
id = g[h-j+i+len];
else
id = g[i+h];
int t = ss.st; for(int v = ; v < j ; ++ v)
{
if (g[i+v] != id)
t &= ~( << (i+v));
else
t |= ( << (i+v)); if (g[i+v+len] != id)
t &= ~( << (i+v+len));
else
t |= ( << (i+v+len)); } if (!vis[t])
{
vis[t] = true;
status ns;
ns.h = A(ns);
ns.step = ss.step + ;
ns.st = t;
q.push(ns);
}
} } }
return -;
} int main(int argc, char * argv[])
{
int T,T2=;
memset(g,,sizeof(g));
scanf("%d",&T);
while (T--)
{
while(!q.empty())
q.pop();
scanf("%d",&len);
scanf("%s%s",g,&g[len]);
memset(vis,false,sizeof(vis));
target = caculate[len*]-;
all = len*;
cout << "Case #" << T2++ << ": " << bfs() << endl;
}
return ;
}
最新文章
- Java中一些常用的方法
- SegmentFault创始人高阳:辍学后带着500元北漂,4年建成国内最大开发者
- 0729pm命名空间
- 介绍UDF,以及完成大小写的转换
- C# 启动关闭.exe进程(转)
- yii框架基本操作
- PHP自学之路---报表及绘图技术
- html5 notifications通知
- c++ primer plus 习题答案(1)
- 配置php网页显示错误
- 关于 vue.js 运行环境的搭建(mac)
- java 中的重载与重写 抽象类与接口的区别
- 图像处理:卷积模块FPGA 硬件加速
- 洛谷P1330封锁阳光大学题解
- C# 字符串大写转小写,小写转大写,数字保留,其他除外
- CSS之设置滚动条样式
- canvas放射粒子效果
- Promise &; Deferred Objects in JavaScript Pt.2: in Practice
- 解题:BZOJ 2818 GCD
- python(24)下载文件