RQ83 魔兽世界
2011年8月16日 00:25
虽然只是普通的BFS，但此题非常神奇！如果通过传送门到一个点，那么点不需要被标记掉。代码又长又乱，几行又删了，凑合看吧.
const
dire:array[1..4,1..2]of integer=((1,0),(0,1),(0,-1),(-1,0));
type
int=longint;
rec=record
x1,x2,y1,y2:int;
step:boolean;
end;
rec2=record
x,y,step:int;
end;
var
i,j,k,xx,yy,n,m,min,head,tail:int;
map:array[1..101,1..101] of char;
hash:array[1..101,1..101] of boolean;
bro:array['A'..'Z'] of rec;
f:array[0..10000] of rec2;
ch:char;
can,add:boolean;
begin
min:=$fffffff;
head:=0;tail:=1;can:=false;
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(map[i][j]);
if map[i,j]>='A' then
begin
if bro[map[i][j]].step=false then
begin
bro[map[i][j]].x1:=i;
bro[map[i][j]].y1:=j;
bro[map[i][j]].step:=true;
end
else
begin
bro[map[i][j]].x2:=i;
bro[map[i][j]].y2:=j;
end;
end;
end;
readln;
end;
f[tail].x:=1;
f[tail].y:=1;
while(head<tail) do
begin
inc(head);
for i:=1 to 4 do
begin
xx:=f[head].x+dire[i][1];
yy:=f[head].y+dire[i][2];
if (xx>=1)and(xx<=n)and(yy>=1)and(yy<=m) then
begin
add:=true;
ch:=map[xx][yy];
if ch<>'1' then
begin
if (ch>='A') then
begin
map[xx][yy]:='1';
if (bro[ch].x1=xx)and(bro[ch].y1=yy) then
begin
xx:=bro[ch].x2;
yy:=bro[ch].y2;
end
else
begin
xx:=bro[ch].x1;
yy:=bro[ch].y1;
end;
end
else
map[xx][yy]:='1';
inc(tail);
f[tail].x:=xx;
f[tail].y:=yy;
f[tail].step:=f[head].step+1;
if (xx=n)and(yy=m) then
begin
if f[tail].step<min then
min:=f[tail].step;
can:=true;
end;
end;
end;
end;
end;
if can then
writeln(min)
else
writeln('No Solution.');
end.