UVa 12569 - Planning Mobile Robot on Tree (EASY Version)(BFS+状态压缩)

有n个结点,一个结点上有机器人,其余结点有的有障碍物,给出结点之间的通路,求最少经过多少步才能让机器人到达目标结点。

很像书上八数码的那道例题,使用一个vis数组保存所有状态,然后进行BFS。不同的是,这这道题要进行状态压缩,否则会超时。

将每个结点是否为空用一个整数记录,然后用另一个记录机器人的位置,只有(1<<maxn)*maxn数量级的数据,就不会超时了。

找到之后递归打印解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=15;
const int maxstate=(1<<maxn)*maxn+10;
int n,m,s,t;
int fa[maxstate],dist[maxstate];
bool vis[1<<maxn][maxn],g[maxn][maxn];
typedef int go[2];
typedef int state[2];
state st[maxstate];
go k[maxstate];
void read(){
memset(g,0,sizeof(g));
memset(k,0,sizeof(k));
memset(fa,0,sizeof(fa));
memset(st,0,sizeof(st));
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
scanf("%d%d%d%d",&n,&m,&s,&t);
st[1][1]=s-1,st[1][0]|=1<<(s-1);//记录初始状态机器人的位置。
for(int i=0;i<m;++i){
int k;
scanf("%d",&k);
st[1][0]|=1<<(k-1);//障碍物的位置。
}
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
g[u-1][v-1]=g[v-1][u-1]=true;
}
return;
}
int bfs(){
int front=1,rear=2;
while(front<rear){
state& s=st[front];
if(s[1]==t-1) return front;
for(int i=0;i<n;++i){
if(!(s[0]&(1<<i))) continue;
for(int j=0;j<n;++j){
if((s[0]&(1<<j))||!g[i][j]) continue;
state& t=st[rear];
memcpy(&t,&s,sizeof(s));
if(s[1]==i) t[1]=j;
t[0]^=1<<i|1<<j;//交换位置。
k[rear][0]=i+1,k[rear][1]=j+1;
dist[rear]=dist[front]+1,fa[rear]=front;//记录父状态。
if(!vis[t[0]][t[1]]) vis[t[0]][t[1]]=true,++rear;
}
}
++front;
}
return 0;
}
void print_ans(int a){
if(!fa[a]) return;//递归至初始状态。
print_ans(fa[a]);
printf("%d %d\n",k[a][0],k[a][1]);
return;
}
int main(){
int t,tt=0;
scanf("%d",&t);
while(t--){
read();
int a=bfs();
printf("Case %d: %d\n",++tt,a?dist[a]:-1);
print_ans(a);
printf("\n");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。