题目大意
w h （w, h <= 16)的网格有 n （ n <= 3) 个小写字母（代表鬼）其余的是‘#’（代表障碍格） 或 ‘ ’（代表空格。 要求把他们移动到对应的大写字母里。每步可以有多个鬼同时移动（均为上下左右4个移动方向之一）， 但每步移动两个鬼不能占用同一个位置， 也不能在一步之内交换位置。输入保证空格联通，障碍联通，且在2 2子网格中至少有一个障碍格，并且最外面一层是障碍格。输入保证有解。
基本原理
Bfs模拟三个小鬼到处乱走的状态即可。
优化
- 我们可以将带障碍的网格图更改为一张由节点和边组成的图，避免了搜索时对障碍的判断。
- 对于状态的判重，不要用stl的set$Olog n$解决，我们要想办法在$O(1)$的时间内判重。建图时图的节点的下标要离散化，不是其在网格图中的位置row * TotCol + col，而是新建出这个节点的序号。这样，由于位置最多有$(2^4)^2=2^8$，所以我们可以如此状态压缩：将第一个小人所在节点的编号|(第二个小人所在节点的编号<<8)|(第三个小人所在节点的编号<<16)。这样我们就可以用数组来判重了。
- 循环总是比递归快。进行状态转移时，不要递归每一个小人的位置。用循环枚举。对于人数<3的情况，将不用的人放到一个孤立点中即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <bitset>
#include <cstdarg>
using namespace std;
const int MAX_ROW = 20, MAX_COL = 16, MAX_ROLE = 3, MAX_EDGE = MAX_ROW * MAX_COL * 4, MAX_STATE = 20000000;
bool IsWall[MAX_ROW][MAX_COL];
int TotRole, TotRow, TotCol;
int Ans;
int Dist1[MAX_STATE], Dist2[MAX_STATE];
struct Node;
struct Edge;
struct Node
{
Edge *Head;
}_nodes[MAX_ROW * MAX_COL];
int _vCount;
Node *_cord[MAX_ROW][MAX_COL];
Node *NewNode(int row, int col)
{
return _cord[row][col] = _nodes + _vCount++;
}
struct Edge
{
Node *To;
Edge *Next;
}_edges[MAX_EDGE];
int _eCount;
void AddEdge(Node *from, Node *to)
{
Edge *e = _edges + ++_eCount;
e->To = to;
e->Next = from->Head;
from->Head = e;
}
struct State
{
Node *Pos[MAX_ROLE];
int Dist;
void Clear()
{
memset(Pos, NULL, sizeof(Pos));
Dist = 0;
}
State() { Clear(); }
bool CanMove(Node **tos)
{
for (int i = 0; i < MAX_ROLE; i++)
for (int j = i + 1; j < MAX_ROLE; j++)
{
if (tos[i] == Pos[j] && tos[j] == Pos[i])
return false;
if (tos[i] == tos[j])
return false;
}
return true;
}
State GetMove(Node **tos)
{
State ans;
for (int i = 0; i < MAX_ROLE; i++)
ans.Pos[i] = tos[i];
return ans;
}
}Start, Target;
queue<State> q1, q2;
void ClearAll()
{
memset(Dist1, -1, sizeof(Dist1));
memset(Dist2, -1, sizeof(Dist2));
while (!q1.empty())
q1.pop();
while (!q2.empty())
q2.pop();
Start.Clear();
Target.Clear();
memset(_nodes, 0, sizeof(_nodes));
memset(_edges, 0, sizeof(_edges));
memset(IsWall, 0, sizeof(IsWall));
_eCount = 0;
Ans = 0;
_vCount = 3;
Start.Pos[0] = _nodes, Start.Pos[1] = _nodes + 1, Start.Pos[2] = _nodes + 2;
Target.Pos[0] = _nodes, Target.Pos[1] = _nodes + 1, Target.Pos[2] = _nodes + 2;
memset(_cord, NULL, sizeof(_cord));
}
void BuildGraph()
{
for (int row = 0; row < TotRow; row++)
for (int col = 0; col < TotCol; col++)
if (!IsWall[row][col] && !_cord[row][col])
NewNode(row, col);
for (int i = TotRole; i < MAX_ROLE; i++)
{
AddEdge(Start.Pos[i], Start.Pos[i]);
AddEdge(Target.Pos[i], Target.Pos[i]);
}
const int Dir[4][2] = { { 1, 0 },{ 0, 1 },{ -1, 0 },{ 0, -1 } };
for (int row = 0; row < TotRow; row++)
for (int col = 0; col < TotCol; col++)
{
if (IsWall[row][col])
continue;
AddEdge(_cord[row][col], _cord[row][col]);
for (int i = 0; i < 4; i++)
{
int row1 = row + Dir[i][0], col1 = col + Dir[i][1];
if (row1 < 0 || row1 >= TotRow || col1 < 0 || col1 >= TotCol)
continue;
if (IsWall[row1][col1])
continue;
AddEdge(_cord[row][col], _cord[row1][col1]);
}
}
}
int State_int(State& S)
{
int state = S.Pos[0] - _nodes | (S.Pos[1] - _nodes << 8) | (S.Pos[2] - _nodes << 16);
return state;
}
void DoNext(State& cur,
int *distIn, int *distOut,
queue<State>& qIn)
{
Node *tos[MAX_ROLE];
for (Edge *e0 = cur.Pos[0]->Head; e0; e0 = e0->Next)
for (Edge *e1 = cur.Pos[1]->Head; e1; e1 = e1->Next)
for (Edge *e2 = cur.Pos[2]->Head; e2; e2 = e2->Next)
{
tos[0] = e0->To, tos[1] = e1->To, tos[2] = e2->To;
if (!cur.CanMove(tos))
continue;
State next = cur.GetMove(tos);
next.Dist = cur.Dist + 1;
int nextS = State_int(next);
if (distIn[nextS] >= 0)
continue;
distIn[nextS] = next.Dist;
if (distOut[nextS] >= 0)
{
Ans = next.Dist + distOut[nextS];
return;
}
qIn.push(next);
}
}
int Bfs()
{
Start.Dist = Target.Dist = 0;
Dist1[State_int(Start)] = Dist2[State_int(Target)] = 0;
q1.push(Start);
q2.push(Target);
while (true)
{
int curDist = q1.front().Dist;
while (q1.front().Dist == curDist)
{
State cur = q1.front();
q1.pop();
DoNext(cur, Dist1, Dist2, q1);
if (Ans)
return Ans;
}
while (q2.front().Dist == curDist)
{
State cur = q2.front();
q2.pop();
DoNext(cur, Dist2, Dist1, q2);
if (Ans)
return Ans;
}
}
return Ans;
}
int main()
{
char s[MAX_COL + 5];
while (scanf("%d%d%d
", &TotCol, &TotRow, &TotRole) && (TotRow || TotCol || TotRole))
{
ClearAll();
for (int row = 0; row < TotRow; row++)
{
memset(s, 0, sizeof(s));
fgets(s, sizeof(s), stdin);
for (int col = 0; col < TotCol; col++)
{
char ch = s[col];
if (ch == '#')
IsWall[row][col] = true;
else if ('a' <= ch && ch <= 'c')
Start.Pos[ch - 'a'] = NewNode(row, col);
else if ('A' <= ch && ch <= 'C')
Target.Pos[ch - 'A'] = NewNode(row, col);
}
}
BuildGraph();
printf("%d
", Bfs());
}
return 0;
}