UVa 12569 - Planning mobile robot on Tree (EASY Version)（BFS＋状态压缩）

发表于 分类于 ， Disqus：

有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博客，格式可能有所偏差。 **

相关文章