专栏首页ACM算法日常Planning mobile robot on Tree (EASY Version)(UVA12569,状态压缩)

Planning mobile robot on Tree (EASY Version)(UVA12569,状态压缩)

题目链接:https://vjudge.net/problem/UVA-12569

题目:

We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable obstacle. The robot and the obstacles may only reside at vertices, although they may be moved across edges. No vertex may ever contain more than one movable entity (robot or obstacles).

In one step, we may move either the robot or one of the obstacles from its current position v to a vacant vertex adjacent to v. Our goal is to move the robot to a designated vertex t using the smallest number of steps possible.

Let us call this graph motion planning with one robot, or GMP1R for short. In this problem, we restrict the graph G to be a tree, namely TMP1R.

Here are some examples (gray circles represent obstacles).

Example 1 (s=1, t=3):

Move the obstacle 2-4, and then move the robot 1-2-3. Total: 3 moves.

Example 2 (s=1, t=4):

Move obstacle 2-5, then 3-2-6, and then move the robot 1-2-3-4. Total: 6 moves.

Example 3 (s=1, t=5):

Move the robot 1-6, then obstacle 2-1-7, then robot 6-1-2-8, then obstacle 3-2-1-6, then 4-3-2-1, and finally robot 8-2-3-4-5. Total: 16 moves.

Input

The first line contains the number of test cases T(T<=340). Each test case begins with four integers n, m, s, t(4<=n<=15, 0<=m<=n-2, 1<=s,t<=n, s!=t), the number of vertices, the number of obstacles and the label of the source and target. Vertices are numbered 1 to n. The next line contains m different integers not equal to s, the vertices containing obstacles. Each of the next n-1 lines contains two integers u and v (1<=u<v<=n), that means there is an edge u-v in the tree.

Output

For each test case, print the minimum number of moves k in the first line. Each of the next k lines contains two integers a and b, that means to move the robot/obstacle from a to b. If there is no solution, print -1. If there are multiple solutions, any will do. Print a blank line after each test case.

翻译&题意:

在n个顶点上给出了一个连通的无向图g。其中一个顶点上有一个移动机器人;该顶点标记为S。其他几个顶点中的每个都包含一个可移动的障碍物。机器人和障碍物可能只存在于顶点,尽管它们可能会跨边移动。任何顶点都不能包含多个可移动实体(机器人或障碍物)。

在一个步骤中,我们可以将机器人或其中一个障碍物从其当前位置v移动到与v相邻的空顶点。我们的目标是使用尽可能少的步骤将机器人移动到指定顶点t。

输入:

T//T个测试样例

n m s t //s机器人一开始的位置,t机器人要走的位置

m行:输入障碍物的位置

n-1行:输入边

输出:输出路径

给出一个样例

输入:

1

4 1 1 3

2

1 2

2 3

2 4

输出

Case 1: 3

2 4

1 2

2 3

思路:

这道题看起来会感觉很懵,没办法下手。如果用简单的搜索就会发现我们很难去判断多个石头的不同状态,但是我们可以先看一看这道题的数据,结点最大只有15个,那么我们可以用一个数字的二进制形式来保存石头和机器人的位置(状态压缩),对于每一次移动后的状态,我们存储起来,就像八数码那题一样,枚举每个障碍物和机器人,一步一步去试探。就可以得出最小的步数了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))

const int maxn=15;//15个结点
const int maxstate=(1<<maxn)*maxn+10;//最多会有多少种状态
int n,m,s,t;
int fa[maxstate],dist[maxstate];//fa数组储存路径,dist数组储存步数
bool vis[1<<maxn][maxn],g[maxn][maxn];//vis

typedef int go[2];
typedef int state[2];

state st[maxstate];//每个状态
go k[maxstate];

void read()//读入数据,初始化
{
    mem(g,0);mem(k,0);mem(fa,0);mem(st,0);mem(vis,0);
    mem(dist,0);

    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;//减去1,因为计算用的是[0,n)的左闭右开区间
    }
    return ;
}

int bfs()
{
    int front=1,rear=2;//bfs这里用的是数组,方便输出路径
    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 &o=st[rear];
                memcpy(&o,&s,sizeof(s));
                if(s[1]==i)o[1]=j;//如果是机器人,就移动机器人的位置到j
                o[0]^=1<<i|1<<j;//交换机器人或者障碍物与空结点

                k[rear][0]=i+1;k[rear][1]=j+1;//储存状态,要+1,方便输出

                dist[rear]=dist[front]+1,fa[rear]=front;
                if(!vis[o[0]][o[1]])//当前状态没搜索过就可以把当前状态给放到队列里
                vis[o[0]][o[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();
        //cout<<a<<endl<<endl;
        printf("Case %d: %d\n",++tt,a?dist[a]:-1);
        print_ans(a);
        printf("\n");
    }
}

总结:

这道题主要凸显在对于状态的压缩上,主要是因为图中有多个点可以去移动,是八数码的加强版(八数码只有一个点可以移动)。好好掌握这道题,可以对状态压缩有更深入的理解。

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:HCHO

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 搜索专题2 | 3D地宫寻路 POJ - 2251

    上一篇我们做了一道棋子摆放的题目,采用的是DFS算法,本篇是一篇BFS算法,在刚开始学习搜索算法的时候,会觉得DFS和BFS算法非常相似,因为都是搜索然后得到结...

    ACM算法日常
  • 独角兽与数列(置换群循环)- HDU 4985

    群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

    ACM算法日常
  • CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

    Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

    ACM算法日常
  • hdu----149850 years, 50 colors(最小覆盖点)

    50 years, 50 colors Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    Gxjun
  • CF思维联系--CodeForces -214C (拓扑排序+思维+贪心)

    题解: 现在有三个工作站,有三种工作,每种工作需要完成前置任务才能进行当前工作,三个工作站之间转换需要花费时间,问将所有任务都完成需要花费的最少时间。一开始可...

    风骨散人Chiam
  • POJ 2594 Treasure Exploration

    Description Have you ever read any book about treasure exploration? Have you ev...

    attack
  • PAT 1034 Head of a Gang (30分) 图的连通分量 + DFS

    One way that the police finds the head of a gang is to check people's phone call...

    vivi
  • 图论--差分约束--POJ 3159 Candies

    风骨散人Chiam
  • Java 实现十进制数转换为二进制

    一个会写诗的程序员
  • Codeforce-Ozon Tech Challenge 2020-D. Kuroni and the Celebration(交互题+DFS)

    After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Ku...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券