3299: [USACO2011 Open]Corn Maze玉米迷宫
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 137 Solved: 59
[Submit][Status][Discuss]
Description
今年秋天，约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子，有些格子种了玉 米，种宥玉米的格子无法通行。
迷宫的四条边界上都是种了玉米的格子，其屮只有一个格子 没种，那就是出口。
在这个迷宫里，有一些神奇的传送点6每个传送点由一对点组成，一旦 走入传送点的某个结点，
机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的，如果你定到了另一头，机器也会把你送回来。
奶牛在一个单位的时间内只能向相邻的四个方向移动一格，不过传送机传送是瞬间完成 的。
现在W西在迷宫里迷路了，她只知道目前的位罝在哪里，请你帮助她用最短的时间走出 迷宫吧。
Input
第一行：两个用空格分开的整数：N和M,2
第二行到N+1行：第i+1行有M个连续的字符，描述了迷宫第i行的信息。其中"#"代 表不能通行的玉米地，
"."代表可以通行的草地，"@"代表贝西的起始位罝，"="代表迷宫出口，
大写字母“A”到“Z”总是成对出现的，代表一对传送点
Output
第一行：一个整数，表示贝西走出迷宫的最短时间，保证逃离迷宮的路线一定存在
Sample Input
5 6
###=##
#.W.##
#.####
#.@W##
######
###=##
#.W.##
#.####
#.@W##
######
Sample Output
3
HINT
从起点向右走，通过w传送，再从另一端 走出迷宫
Source
题解：做过无数道BFS迷宫类水题了，但是这个比较神奇一点。。。其实就是多个传动点之间的瞬间传送，别的没了。。
const dd:array[..,..] of longint=((,),(-,),(,-),(,));
var
i,j,k,l,m,n,x0,y0,x1,y1,x,y,f,r:longint;
a,b:array[..,..] of longint;
tr:array[..,..] of longint;
d:array[..,..] of longint;
ch:char;
procedure trans(z:longint;var x,y:longint);
begin
if (z<) or (z>) then exit;
if (tr[z,]=x) and (tr[z,]=y) then
begin
x:=tr[z,];y:=tr[z,];
end
else if (tr[z,]=x) and (tr[z,]=y) then
begin
x:=tr[z,];y:=tr[z,];
end;
end;
begin
readln(n,m);
fillchar(a,sizeof(a),-);
fillchar(tr,sizeof(tr),);
for i:= to n do
begin
for j:= to m do
begin
read(ch);
case upcase(ch) of
'#':a[i,j]:=;
'.':a[i,j]:=;
'=':begin
x1:=i;y1:=j;
a[i,j]:=;
end;
'@':begin
x0:=i;y0:=j;
a[i,j]:=;
end;
'A'..'Z':begin
a[i,j]:=ord(ch)-;
if tr[a[i,j],]= then
begin
tr[a[i,j],]:=i;
tr[a[i,j],]:=j;
end
else
begin
tr[a[i,j],]:=i;
tr[a[i,j],]:=j;
end;
end;
end;
end;
readln;
end;
f:=;r:=;d[,]:=x0;d[,]:=y0;b[x0,y0]:=;
while f<r do
begin
for i:= to do
begin
x:=d[f,]+dd[i,];
y:=d[f,]+dd[i,];
if (x<) or (x>n) or (y<) or (y>m) then continue;
if abs(a[x,y])= then continue;
trans(a[x,y],x,y);
if b[x,y]= then
begin
b[x,y]:=b[d[f,],d[f,]]+;
d[r,]:=x;d[r,]:=y;
if (x=x1) and (y=y1) then
begin
writeln(b[x,y]-);
halt;
end;
inc(r);
end;
end;
inc(f);
end;
end.