uva 12569 Planning mobile robot on Tree (EASY Version) bfs+状态压缩

缘起

关注了 ACM算法日常 这个公众号, 它分享了一篇文章, 就是 uva 12569 Planning mobile robot on Tree (EASY Version) 看了下,有点意思, 就自己做了.

分析

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
有一棵n（4<=n<=15）个结点的树，每个节点标号为1~n, 其中一个结点s(1<=s<=n)有一个机器人，还有一些结点
有石头。每步可以把一个机器人或石头移到一个相邻的节点。任何情况下一个结点里不能有两个东西（石头或机器
人）。输入每个石头的位置和机器人的起点和终点，求最小步数的方案。如果有多解，可以输出任意解。
每个方案之后打印空格.

【输入】
多样例. 首先是样例数. 然后每个样例首先是n,m,s,t,
4 ≤ n ≤ 15, 0 ≤ m ≤ n − 2, 1 ≤ s, t ≤ n, s ̸= t
分别表示顶点的个数, 石子的个数, 机器人的起点和终点. 然后是m个正整数表示石头的位置, 最后是n-1行
分别表示树的边

【输出】
对每个样例, 打印最少的步数, 然后是k行表示移动方案. 每行是a b 这种. 表示把a处的石头或者机器人移动
到b, 如果无解的话, 输出-1, 如果有多个解的话, 输出任意一种方案即可. 每个case之后打印一个空行

【样例输入】
3
4 1 1 3
2
1 2
2 3
2 4
6 2 1 4
2 3
1 2
2 3
3 4
2 5
2 6
8 3 1 5
2 3 4
1 2
2 3
3 4
4 5
1 6
1 7
2 8

【样例输出】
Case 1: 3
2 4
1 2
2 3

Case 2: 6
2 5
3 2
2 6
1 2
2 3
3 4

Case 3: 16
1 6
2 1
1 7
6 1
1 2
2 8
3 2
2 1
1 6
4 3
3 2
2 1
8 2
2 3
3 4
4 5

【限制】
10s

其实对于懂搜索的人来讲. 思路是很明显的. 就是bfs, 唯一需要注意的是, 怎么哈希? 即判重? 因为n较小, 所以考虑二进制压缩状态. 用s来维护机器人的状态, 然后一个正整数表示当前哪个节点有石头. 有石头的记1, 否则记0.

即用s和一个不超过 1<<15 的非负整数表示当前状态. 然后bfs即可

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//#include "stdafx.h"
#include <stdio.h>
#include <queue>
using namespace std;
#include <vector>
#include <string.h>
//#define LOCAL

const int maxn = (1<<4)+5, maxm = (1<<15)+10;
int n,m,s,t, ss, u[maxn], v[maxn]; // ss表示石子的初始状态
bool visited[maxn][maxm]; // v[s][ss]=true 表示机器人在s处, 石子状态是zz这种状态已经访问过了

struct Edge
{
	int x,i,j; // x是终点, i是边的编号,j是正反（到底是从u到v还是从v到u, 1表示u[i]到v[i], -1表示v[i]到u[i]）
	Edge(int x, int i, int j):x(x),i(i),j(j){}
};
vector<Edge> g[maxn];

typedef vector<Edge>::iterator vit;

typedef struct Node
{
	int x, zz, level, i, j; // 机器人的位置,石子的状态, level是当前移动的步数, i表示从当前节点的父节点转移过来是通过i这条边,而边的方向由j刻画(j=1表示u[i]到v[i],j=-1表示v[i]到u[i])
	Node *fa; // bfs中的前驱
	Node(int x, int zz, int i, int j, int level, Node *fa):x(x),zz(zz),fa(fa),i(i), j(j), level(level){}
}*nd;

void printsol(nd cur) // 递归打印解
{
	if (cur->x==s && cur->zz==ss) // 如果回到了最初的状态
	{
		return;
	}
	printsol(cur->fa);
	if (~cur->j) // 如果是正向的话
	{
		printf("%d %d\n", u[cur->i], v[cur->i]);
	}
	else
	{
		printf("%d %d\n", v[cur->i], u[cur->i]);
	}
}

void bfs()
{
	queue<nd> q;
	nd node = new Node(s,ss, 0,0, 0, 0);
	q.push(node);
	visited[s][ss] = true;
	while(!q.empty())
	{
		nd front = q.front();
		q.pop();
		if (front->x==t) // 机器人抵达终点
		{
			printf("%d\n", front->level);
			printsol(front); // 打印解
			puts("");
			return;
		}
		for (vit e = g[front->x].begin(); e!=g[front->x].end(); e++)
		{
			if (!(1<<e->x-1 & front->zz) && !visited[e->x][front->zz]) // 如果想去之处没有石子并且该状态并没有去过
			{
				nd nxt = new Node(e->x, front->zz, e->i, e->j, front->level+1, front);
				visited[e->x][front->zz] = true;
				q.push(nxt);
			}
		} // 机器人的转移
		for (int k = 0; k<n; k++)
		{
			if (!(1<<k & front->zz)) // 如果该位置没有石子
			{
				continue;
			}
			for (vit e = g[k+1].begin(); e!=g[k+1].end(); e++)
			{
				int zz;
				if (!(1<<e->x-1 & front->zz) && e->x!=front->x && !visited[front->x][zz=front->zz & ~(1<<k) | (1<<e->x-1)]) // 如果想去的地方没有石子, 而且也不是机器人目前在的地方 而且该状态尚未搜索过
				{
					nd nxt = new Node(front->x,zz, e->i, e->j, front->level+1, front);
					visited[front->x][zz] = true;
					q.push(nxt);
				}
			} // 转移处于k位置的石子
		} // 石子的转移
	}
	puts("-1\n");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		memset(visited, 0, sizeof(visited));
		ss = 0;
		for (int i = 1; i<=15; i++)
		{
			g[i].clear();
		}
		scanf("%d%d%d%d", &n,&m,&s,&t);
		while(m--)
		{
			int x;
			scanf("%d", &x);
			ss |= 1<<x-1;
		} // 初始石子状态
		for (int i = 1,x,y;i<=n-1; i++)
		{
			scanf("%d%d",&x, &y);
			u[i] = x, v[i] = y;
			g[x].push_back(Edge(y,i,1));
			g[y].push_back(Edge(x, i, -1));
		}
		printf("Case %d: ", i);
		bfs();
	}
	return 0;
}

ac情况

Status Accepted
Time 1690ms
Length 2721
Lang C++11 5.3.0
Submitted 2019-10-04 22:05:43
Shared
RemoteRunId 23998810