搜索算法_PROBLEM
今天胡老说考搜索就是考暴力，没有分的就不用来了，结果最后。。。
我是唯一有分的，GG。
第三道题太难了，我就不写了。。。
魔法数字
（A.pas/.c/.cpp）
时间限制：1.0s，空间限制131072 KB
题目描述：
给一个六位数A 和另外一个六位数B.
你有一根魔法棒，初始时指向A 的最左边数字，每一次你可以选择下列操作
之一：
1.将当前魔杖指向的数字与最左端的一个数字调换位置。
2.将当前魔杖指向的数字与最右端的一个数字调换位置。
3.将当前魔杖指向的数字+1。(若当前魔杖指向的数字为9 则无效)
4.将当前魔杖指向的数字−1。(若当前魔杖指向的数字为0 则无效)
5.将当前魔杖向右移动一位。
6.将当前魔杖向左移动一位。
输入描述：
多组数据，处理到EOF
对于每组数据，包含两个6 位数A,B
输出描述：
对于每组数据，输出一行表示答案..
样例输入：
1
123456 654321
样例输出：
11
数据范围：
100%的数据保证：1 <= 数据组数 <= 200
题解
直接暴力搜索所有数字？不可行
只需要考虑这些数字在哪些位置是否出现过，6^6状态
code
#include<cstdio>
#include<cstring>
const int maxn=1000005;
const int HASH=1428571;
struct data{
int k,v;
bool a[6];
}q[maxn];
int vis[HASH+1],v[maxn],tennum[8]={1000000},sum[8],num[8],a,b,head,tail,LM;
bool judge(int u){
int h=q[u].v%HASH,t=vis[h];
while(t!=-1){
if(q[u].v==q[t].v)return 0;
t=v[t];
}
v[u]=vis[h],vis[h]=u;
return 1;
}
void FH(data u,int k){
q[tail].k=u.k+1,q[tail++].a[k]=1;
}
void FS(int f,int k,int id,data u){
if(f){
q[tail]=u;
int t=num[k],v=0;num[k]=num[id],num[id]=t;
for(register int i=0;i<=6;++i)v+=num[i]*tennum[i];
q[tail].v=v;
if(judge(tail))FH(u,k);
num[id]=num[k],num[k]=t;
}
}
void FT(int f,data p,int u){
q[tail]=p;
int v=LM+f;
q[tail].v=v;
if(judge(tail))FH(p,u+f);
}
int bfs(){
head=0,tail=1;
judge(head);
while(head<tail){
data p=q[head++];
LM=p.v;
for(register int i=6;i>=0;--i)num[i]=p.v%10,p.v/=10;
int u=num[6],f;
f=1;
if((!num[u])||(!u))f=0;
FS(f,0,u,p);
f=1;
if(((!num[5])&&(!u))||u==5)f=0;
FS(f,5,u,p);
if(u<5)FT(1,p,u);
if(u) FT(-1,p,u);
}
return tail;
}
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
for(register int i=1;i<=6;++i)
tennum[i]=tennum[i-1]/10;
while(scanf("%d%d",&a,&b)!=EOF){
memset(vis,-1,sizeof(vis));
memset(q[0].a,0,sizeof(q[0].a));
q[0].v=a*10,q[0].k=0,q[0].a[0]=1;
for(register int i=5;i>=0;--i)sum[i]=b%10,b/=10;
int res=bfs(),ans=999999;
for(register int i=0;i<res;++i){
q[i].v/=10;
int num[6],rez=q[i].k;
for(register int j=5;j>=0;--j){
num[j]=q[i].v%10;
q[i].v/=10;
}
for(register int k=0;k<6;++k)
if(sum[k]!=num[k]&&!q[i].a[k]){
rez=999999;break;
}else rez+=((sum[k]-num[k])>0?(sum[k]-num[k]):-(sum[k]-num[k]));
ans=ans>rez?rez:ans;
}
printf("%d\n",ans);
}
return 0;
}BitMask
（B.pas/.c/.cpp）
时间限制： 3.0s，空间限制 131072 KB
题目描述：
给出 2 x n的方格，每个方格初始都没有颜色，每次你可以选择其中一矩形区域，将其涂成某个颜色 C，现给出最终状态，请问少需要多步能到达 最终状态？
输入描述：
输入第一行为一个整数T，表示数据组数
对于每组数据输入的第一行表示n( 1 <= n <= 8 )，接下来 2行，每个一长度n的字符串，保证字符串只包含大写字母
输出描述：
对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 。
样例输入：
3
3
ABA
CBC
3
BAA
CCB
3
BBB
BAB
样例输出：
3
3
2
数据范围：
50%的数据保证： 1 <= T <= 200且 n是随机产生的 是随机产生的
50%的数据保证： 1 <= T <= 25 且 n 为 8
题解
直接暴力BFS即可，每次抽取一个矩形进行位运算即可
code
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(register int i=x;i<y;++i)
#define CM(x,v) memset((x),v,sizeof(x))
char mp[3][10];
bool vis[27];
int t,n,m,head,tail,tot,u,v,dis[1<<17],Q[1<<19];
void bfs(int x){
CM(dis,-1);
head=tail=dis[x]=0;
Q[tail++]=x;
while(head!=tail){
u=Q[head++];
rep(F1,0,n)rep(F2,F1,n)rep(F3,0,2)rep(F4,F3,2){
CM(vis,0),tot=0;
rep(i,F3,F4+1)rep(j,F1,F2+1){
if(tot>1)break;
if((u&(1<<(i*n+j))))continue;
if(!vis[mp[i][j]-'A'])++tot,vis[mp[i][j]-'A']=1;
}
if(tot==1){
v=u;
rep(i,F3,F4+1)rep(j,F1,F2+1)v|=1<<(i*n+j);
if(dis[v]==-1){
dis[v]=dis[u]+1;
if(v==m)return;
if(dis[v]<(n<<1))Q[tail++]=v;
}
}
}
}
}
template<class T>inline void readin(T &res){
static char ch;T flag=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
inline void readst(char x[]){
static char ch;int len=0;
while((ch=getchar())<'A'||ch>'Z');x[len++]=ch;
while((ch=getchar())>='A'&&ch<='Z')x[len++]=ch;
}
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
readin(t);
while(t--){
readin(n),readst(mp[0]),readst(mp[1]);
m=(1<<(n<<1))-1,bfs(0);
printf("%d\n",dis[m]);
}
return 0;
}BruteForce
只有一组测试数据，保证 T<= 10且 n=12的数据不超过 2组， n=11的数据不的数据不的数据不超过2组
题解
首先暴力的求出环的方案数
之后暴力枚举环之后缩点用Matrix-Tree定理计算生成树即可
没有code
MARK一下MARIX—TREE