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");
    }
}

总结：

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