Maze
【题目描述】
众所周知（怎么又是众所周知），仙剑的迷宫是难走的要命，某人就在仙四的女罗岩困了很长时间。
我们可以把女罗岩的地图抽象成n*n的地图，我们现在在（1,1）处，而出口在(n,n)。每次行动只能向上下左右移动一格。图中有M个机关，只有打开某个机关之后，与该机关相对应的地方才可以行走。当然，地图中还会有小怪兽，他们能够监视着他所在地区以及上下左右共五个方格，我们不愿意与他们战斗（为了节省时间），所以他们能监视到的地方不可以行走。同样的，地图上的障碍物处也不能经过。
我们需要求出从起点到终点的最少步数。
【输入格式】
第1行，两个整数N, M。表示地图大小为N*N，机关的数量为M。
第2-N+1行，每行N个整数，每个整数i可能是0，-1，-2或者一个正整数。i=0表示该位置为一块空地，i=-1表示该位置为一个障碍物，i=-2表示该位置为一个小怪兽。如果i是一个属于[1,M]的正整数，则表示该位置为一个机关，其编号为i。如果i是一个大于M的正整数，则表示该位置为一个机关控制区域，它由编号为i-M的机关控制。
【输出格式】
一个整数，为走出迷宫所需的最少的步数。
【输入样例】
6 2
0 0 0 -2 -1 2
-1 0 0 0 -1 0
-2 0 0 0 3 3
-2 0 0 -1 -1 4
0 -1 0 0 -1 0
1 0 0 0 -1 0
【输出样例】
24
【样例说明】
地图如下图，S为入口，T为目标，黑色的单元格为障碍物。每个E表示一个小怪兽，(E)为小怪兽的监视范围。K1表示机关1，K2表示机关2。D1表示机关为1的控制区域，D2表示机关为2的控制区域。
最优的路线为(1,1) →(1,2) →(2,2) →(2,3) →(3,3) →(4,3) →(5,3) →(6,3) →(6,2) →(6,1)(破坏供电1) →(6,2) →(6,3) →(5,3) →(4,3) →(3,3) →(3,4) →(3,5) →(3,6) →(2,6) →(1,6)(破坏供电2) →(2,6) →(3,6) →(4.6) →(5,6) →(6,6)
【数据规模】
1<=N<=50
0<=M<=16
这是一个经典的模型，需要记录地图的迷宫问题。
首先，迷宫问题一般都是 BFS ，这个当然也不例外。
然后，平常做迷宫问题的时候，只需要在队列中记录一下横纵坐标就可以了，但这种问题，还需要记录一下拿了那些钥匙，当然，是用位运算来记录的。一共有 16 把钥匙，也就最大是 2^16-1 ，所以可以记录的下。
然后，当扩展时，怪兽及怪兽能看到的一定不能扩展，需要钥匙的，如果有钥匙就可以扩展，是钥匙的，用位运算把它加上去。
然后，然后就是这样。
晒一下 （XMC）的代码。
const
bx:array[1..4] of integer=(1,-1,0,0);
by:array[1..4] of integer=(0,0,1,-1);
type
ll=record
x,y:integer;
d,z:longint;
end;
var
i,j,k,n,m:longint;
v:array[0..51,0..51,0..65536] of boolean;
q:array[0..1000001] of ll;
map:array[0..51,0..51] of integer;
aa,x,y,d,z,xx,yy,head,tail,zz:Longint;
procedure init;
begin
readln(n,m);
fillchar(map,sizeof(map),0);
for i:=1 to n do
for j:=1 to n do
begin
read(aa);
if map[i,j]<>-1 then map[i,j]:=aa;
if aa=-2 then
begin
map[i,j]:=-1;
for k:=1 to 4 do
begin
xx:=i+bx[k];
yy:=j+by[k];
if (xx in[1..n]) and (yy in [1..n]) then
map[xx,yy]:=-1;
end;
end;
end;
end;
procedure main;
begin
v[1,1,0]:=true;
head:=0;
tail:=1;
q[1].x:=1;
q[1].y:=1;
q[1].z:=0;
q[1].d:=0;
while head<>tail do
begin
if head=1000000 then head:=1 else inc(head);
x:=q[head].x;
y:=q[head].y;
d:=q[head].d;
z:=q[head].z;
for i:=1 to 4 do
begin
xx:=x+bx[i];
yy:=y+by[i];
if (xx in [1..n]) and (yy in [1..n]) and (map[xx,yy]>=0) and (not v[xx,yy,z])then
begin
if (xx=n) and (yy=n) then
begin
writeln(d+1);
close(input);
close(output);
halt;
end;
if (map[xx,yy]=0) and (not (v[xx,yy,z])) then
begin
v[xx,yy,z]:=true;
if tail=1000000 then tail:=1 else inc(tail);
q[tail].x:=xx;
q[tail].y:=yy;
q[tail].z:=z;
q[tail].d:=d+1;
continue;
end;
if (map[xx,yy]<=m) and
((z and (1<<(map[xx,yy]-1))=0) or
((z and (1<<(map[xx,yy]-1))<>0) and (not v[xx,yy,z]))) then
begin
if z and (1<<(map[xx,yy]-1))=0 then zz:=z+(1<<(map[xx,yy]-1))
else zz:=z;
v[xx,yy,zz]:=true;
if tail=1000000 then tail:=1 else inc(tail);
q[tail].x:=xx;
q[tail].y:=yy;
q[tail].z:=zz;
q[tail].d:=d+1;
continue;
end;
if (map[xx,yy]>m) and (z and (1<<(map[xx,yy]-m-1))<>0) and (not v[xx,yy,z]) then
begin
v[xx,yy,z]:=true;
if tail=1000000 then tail:=1 else inc(tail);
q[tail].x:=xx;
q[tail].y:=yy;
q[tail].z:=z;
q[tail].d:=d+1;
continue;
end;
end;
end;
end;
end;
begin
assign(input,'maze.in');reset(input);
assign(output,'maze.out');rewrite(output);
init;
main;
close(input);
close(output);
end.
另，存稀疏图不一定非要用邻接表，也可以用边表。（也就是开一个边数那么大的数组，存每一条边的起点、终点、权值，这个方法比邻接表要慢，但是他比邻接表好写，还省内存（如果你用正常的链表而不是模拟链表的话当我没说），对于我这种邻接表经常写挂的人来说很好用）