https://vjudge.net/problem/UVA-1601

题目

你在游乐场的鬼屋里当操作员，专门控制鬼屋里的机器人……某日没事干的出题人把这些机器人搬到了其他地方，你需要在最短的时间内遥控机器人让他们回到原位。所有机器人都可以同时在1秒内朝四个方向（上下左右）移动1格，但是每次移动都必须符合以下条件

1. 每个格子只能有一个机器人
2. 任意两个机器人的位置不能交换
3. 不能移动到墙里……

问你需要至少多少时间才能把所有机器人归位。

输入包含多组数据

地图的宽、高和机器人的数量

下面几行表示地图，其中小写字母表示机器人的位置，大写字母表示机器人的终点，'#'表示墙,' '表示可以走的位置……

输出每组数据下的最短时间

样例输入

15 5 2
2#####
3#A#B#
4#   #
5#b#a#
6#####
716 4 3
8################
9## ########## ##
10#    ABCcba    #
11################
1216 16 3
13################
14### ##    #   ##
15##  #  ##   # c#
16#  ## ########b#
17# ##  # #   #  #
18#   # ##  # # ##
19## a# #   # #  #
20### ## #### ## #
21##   #   #  #  #
22#  ##### # ## ##
23####   #B# #   #
24##  C#   #   ###
25#  # # ####### #
26# ######  A##  #
27#        #    ##
28################
290 0 0

 样例输出

17
236
377

 题解

只用了一个单向bfs，对空格编号建图，用前向星……

检测能否互换需要分n=2和n=3两种情况考虑

n=2时很简单

n=3时要考虑$\binom{3}{2}$种情况，头晕还多想了3个位置都换了的情况，其实这是不可能的，由于只能移动一步，所以加上这个这只是浪费时间……

AC代码（1080ms，去掉浪费时间的部分是750ms）

1#include<bits/stdc++.h>
2using namespace std;
3#define REP(i,x,y) for(register int i=(x); i<(y); i++)
4#define REPE(i,x,y) for(register int i=(x); i<=(y); i++)
5#ifdef sahdsg
6#define DBG(a,...) printf(a, ##__VA_ARGS__)
7#else
8#define DBG(a,...) (void)0
9#endif
10
11#define MAXN 20
12#define MAXP 300
13int w,h,n;
14int cnt;
15int mp[MAXN][MAXN];
16int st[3],ed[3];
17bool vis[MAXP][MAXP][MAXP];
18int hed[131072], nxt[131072], poi[131072], fstar=0;
19inline void conn(int f, int t) {
20	nxt[fstar]=hed[f];
21	poi[fstar]=t;
22	hed[f]=fstar++;
23}
24struct node {
25	int s;
26	int p[3];
27	node(int *x, int y=0):s(y) {memcpy(p,x,sizeof p);}
28};
29inline void bfs() {
30	memset(vis,0,sizeof vis);
31	queue<node> q;
32	q.push(node(st));
33	int ans=-1;
34	while(!q.empty()) {
35		node now = q.front();q.pop();
36		if(memcmp(now.p,ed,sizeof ed)==0) {ans=now.s; break;}
37		int i[3],k[3],dis[3];
38		REP(i,0,n) dis[i]=now.p[i];
39		memset(k,0,sizeof k);
40		#define CHK k[0]!=k[1] && k[1]!=k[2] && k[2]!=k[0]
41		for(i[0]=hed[now.p[0]]; ~i[0]; i[0]=nxt[i[0]]) {
42			k[0]=poi[i[0]];
43			if(n>=2) for(i[1]=hed[now.p[1]]; ~i[1]; i[1]=nxt[i[1]]) {
44				k[1]=poi[i[1]];
45				if(n>=3) for(i[2]=hed[now.p[2]]; ~i[2]; i[2]=nxt[i[2]]){
46					k[2]=poi[i[2]];
47					if(!vis[k[0]][k[1]][k[2]]) if(CHK) {
48						if(dis[0]==k[1] && dis[1]==k[0]) continue;
49						if(dis[0]==k[2] && dis[2]==k[0]) continue;
50						if(dis[1]==k[2] && dis[2]==k[1]) continue;
51						
52						int j[3],l[3];
53						memcpy(j,k,sizeof j);memcpy(l,dis,sizeof j);
54						sort(j,j+3);sort(l,l+3);
55						if(memcmp(j,l,sizeof j)==0) continue;
56						vis[k[0]][k[1]][k[2]]=1;
57						q.push(node(k,now.s+1));
58					}
59				}
60				else if(!vis[k[0]][k[1]][0]) if(k[0]!=k[1]) {
61					if(k[0]==dis[1] && k[1]==dis[0]) continue;
62					vis[k[0]][k[1]][0]=1; q.push(node(k,now.s+1));
63				}
64			} else if(!vis[k[0]][0][0]){vis[k[0]][0][0]=1; q.push(node(k,now.s+1));}
65		}
66	}
67	printf("%d\n", ans);
68}
69int main() {
70	#ifdef sahdsg
71	freopen("in.txt", "r", stdin);
72	#endif
73	while(~scanf("%d%d%d", &w, &h, &n) && w) {
74		cnt=0;
75		memset(hed,-1,sizeof hed);
76		memset(st,0,sizeof st);
77		memset(ed,0,sizeof ed);
78		fstar=0;
79		REP(i,0,h) REP(j,0,w) {
80			char ch = getchar();
81			if(ch<' ')ch=getchar();
82			if(ch=='#') {mp[i][j]=-1; continue;}
83			mp[i][j]=cnt;
84			if(ch>='a' && ch<='z') st[ch-'a']=cnt;
85			else if(ch>='A' && ch<='Z') ed[ch-'A']=cnt;
86			conn(cnt,cnt);
87			if(i>0 && mp[i-1][j]>=0) conn(mp[i-1][j],cnt),conn(cnt,mp[i-1][j]);
88			if(j>0 && mp[i][j-1]>=0) conn(mp[i][j-1],cnt),conn(cnt,mp[i][j-1]);
89			cnt++;
90		}
91		bfs();
92	}
93	
94	return 0;
95}

 比较慢，可以用双向bfs或A*优化……