链接：http://www.lightoj.com/volume_showproblem.php?problem=1055
类似推箱子的游戏，一条命令可以让abc三个小人同时移动，但是出界或者撞墙是不移动的，求abc到达终点x所需要的最小步数。
我这里用六维的vis来标记这个点走过没，直接上代码
#include<bits/stdc++.h> using namespace std; int n; char mp[12][12]; bool vis[12][12][12][12][12][12]; struct node { int ax, ay, bx, by, cx, cy, step; }; node s; int bfs() { int nx[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; queue<node>Q; s.step = 0; Q.push(s); while(!Q.empty()) { s = Q.front(); Q.pop(); if(mp[s.ax][s.ay]=='X'&&mp[s.bx][s.by]=='X'&&mp[s.cx][s.cy]=='X') return s.step; for(int i = 0; i < 4; i++) { node t; t.ax = s.ax + nx[i][0], t.bx = s.bx + nx[i][0], t.cx = s.cx + nx[i][0]; t.ay = s.ay + nx[i][1], t.by = s.by + nx[i][1], t.cy = s.cy + nx[i][1]; if(t.ax<0||t.ax>=n) t.ax = s.ax; if(t.ay<0||t.ay>=n) t.ay = s.ay; if(t.bx<0||t.bx>=n) t.bx = s.bx; if(t.by<0||t.by>=n) t.by = s.by; if(t.cx<0||t.cx>=n) t.cx = s.cx; if(t.cy<0||t.cy>=n) t.cy = s.cy; for(int j = 1; j <= 3; j++) //这里循环3是因为不能让3个小人重合，若循环1次因为走位的次序不同可能还会重合 { if(mp[t.ax][t.ay]=='#'||(t.ax==t.bx&&t.ay==t.by)||(t.ax==t.cx&&t.ay==t.cy)) t.ax=s.ax, t.ay=s.ay; if(mp[t.bx][t.by]=='#'||(t.bx==t.ax&&t.by==t.ay)||(t.bx==t.cx&&t.by==t.cy)) t.bx=s.bx, t.by=s.by; if(mp[t.cx][t.cy]=='#'||(t.cx==t.bx&&t.cy==t.by)||(t.cx==t.ax&&t.cy==t.ay)) t.cx=s.cx, t.cy=s.cy; } if(vis[t.ax][t.ay][t.bx][t.by][t.cx][t.cy]) continue; vis[t.ax][t.ay][t.bx][t.by][t.cx][t.cy] = 1; t.step = s.step+1; Q.push(t); } } return -1; } int main() { int cas = 0, t; cin>>t; while(t--) { scanf("%d", &n); memset(vis, 0, sizeof vis); for(int i = 0; i < n; i++) scanf("%s", mp[i]); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { if(mp[i][j] == 'A') s.ax = i, s.ay = j; if(mp[i][j] == 'B') s.bx = i, s.by = j; if(mp[i][j] == 'C') s.cx = i, s.cy = j; } vis[s.ax][s.ay][s.bx][s.by][s.cx][s.cy] = 1; printf("Case %d: ", ++cas); int ans = bfs(); if(ans==-1) puts("trapped"); else printf("%d ", ans); } return 0; }