# Planning mobile robot on Tree (EASY Version)（UVA12569，状态压缩)

## 题目：

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.

## 输入：

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

## 思路：

```#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];

{
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--)
{
int a=bfs();
//cout<<a<<endl<<endl;
printf("Case %d: %d\n",++tt,a?dist[a]:-1);
print_ans(a);
printf("\n");
}
}
```

## 总结：

0 条评论

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

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

• ### 独角兽与数列（置换群循环）- HDU 4985

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

• ### CodeForces 982F：The Meeting Place Cannot Be Changed（有向图）

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

• ### hdu----149850 years, 50 colors(最小覆盖点)

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

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

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

• ### POJ 2594 Treasure Exploration

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

• ### 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...

• ### 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...