题目描述

小A在WOW中是个小术士.作为一名术士,不会单刷副本是相当丢脸的.所谓单刷副本就是单挑BOSS了,这么有荣誉感的事小A怎么会不做呢?于是小A来到了厄运之槌开始了单刷.小A看了看,厄运之槌的地图是一个N*M的矩形（N，M<=100）,上面遍布了小怪和传送门.例如（1表示有小怪，0表示无小怪,大写字母表示传送门,传送门:例如,走到 B 传送门点将传送到另一个 B 传送点（次数无限，但每次进入传送点只传送过去，不会在传送回来）数据保证每个传送门有且仅有相对应的另一个传送门）:

　　而入口在左上方（1，1）,BOSS却躲在右下方（N，M）.小A非常急切的想要完成单刷然后去向其他那些战士啊盗贼啊不会单刷的职业炫耀炫耀,所以呢,小A绝不会在小怪身上浪费时间(当然是绕开他们),并且想通过传送门尽快到达BOSS身边.看啊看,想啊想,还是没找出最快的路.终于,灵机一动,想什么啊,编程呗!

输入

第一行2个数据：n m；
　　下面n行，每行m个数（入口点和BOSS点无怪和传送门），表示厄运之槌的地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点,右下角为出口点.
3 4
0000
00A0
A000

输出

一个整数，表示小A最少需要走多少步。如果小A不能走到目标，则输出No Solution.
4

思路

这题的主体是一个不难的bfs，只是在有传送门时就一定要传送而已，但是如果不判重会超时。。。
那么问题来了，如果要判重的话会出现很多奇怪的错误：
1.如果进入传送门时给目标点加上标记，会错，要给进入的点加标记
2.如果给一个封闭的点加标记，而这个点的两侧有门，也会错，这里要特殊判断一下

const
  dx:array[1..4] of integer=(0,1,0,-1);
  dy:array[1..4] of integer=(1,0,-1,0);
var
  a:array[0..101,0..101] of char;
  t:array[-10..30000,1..2] of longint;
  state:array[0..30000] of longint;
  xx:array[1..101,1..101] of longint;
  oo:array['A'..'Z'] of longint;
  i,j,k,n,m:longint;
  ch:char;
  f,fl:boolean;
  st:string;
procedure bfs;
var
  head,tail,i,j,k:longint;
begin
  head:=0; tail:=1;
  t[1][1]:=1; t[1][2]:=1;
  if a[1][1]<>'0' then
    begin
      for i:=1 to n do
      begin
        for j:=1 to n do
          if (a[i,j]=a[1,1]) and (i<>1) or (j<>1) then
            begin
              f:=true;
              break;
            end;
          if f then
            begin
              t[1][1]:=i;
              t[1][2]:=j;
              break;
            end;
        end;
    end;
  while (head<=tail) do
    begin
      inc(head);
      if (t[head,1]=5) and (t[head,2]=11) then
        f:=false;
      for i:=1 to 4 do
        if (t[head][1]+dx[i]>=1) and (t[head][1]+dx[i]<=n) and (t[head][2]+dy[i]>=1) and (t[head][2]+dy[i]<=m) and (a[t[head][1]+dx[i],t[head][2]+dy[i]]<>'1') and (xx[t[head][1]+dx[i],t[head][2]+dy[i]]=0) then
          begin
            if (a[t[head][1]+dx[i],t[head][2]+dy[i]]>='A') and ((a[t[head][1]+dx[i],t[head][2]+dy[i]]<='Z')) then
              begin
                ch:=a[t[head][1]+dx[i],t[head][2]+dy[i]];
                f:=false;
                for j:=1 to n do
                begin
                  for k:=1 to m do
                    if (a[j,k]=ch) and ((j<>t[head][1]+dx[i]) or (k<>t[head][2]+dy[i])) then
                    begin
                      f:=true;
                      break;
                    end;
                  if f then break;
                end;
                inc(tail);
                t[tail][1]:=j;
                t[tail][2]:=k;
               // if (oo[a[t[tail,1],t[tail,2]]]>4) then
                xx[t[head][1]+dx[i],t[head][2]+dy[i]]:=1; //else inc(oo[a[t[head,1],t[head,2]]]);
                state[tail]:=state[head]+1;
                if (t[tail][1]=n) and (t[tail][2]=m) then
                  begin
                    writeln(state[tail]);
                    fl:=true;
                    exit;
                  end;
              end;
            if (a[t[head][1]+dx[i],t[head][2]+dy[i]]='0') then
            begin
            inc(tail);
            t[tail][1]:=t[head][1]+dx[i];
            t[tail][2]:=t[head][2]+dy[i];
            f:=false;
            for j:=1 to 4 do
              if a[t[tail][1]+dx[j],t[tail][2]+dy[j]]='0' then f:=true;
            if f then
            xx[t[tail][1],t[tail][2]]:=1;
            state[tail]:=state[head]+1;
            if (t[tail][1]=n) and (t[tail][2]=m) then
                  begin
                    writeln(state[tail]);
                    fl:=true;
                    exit;
                  end;
            end;
            end;

    end;
end;
begin
  //assign(input,'way5.in'); reset(input);
  readln(n,m);
  for i:=1 to n do
    begin
      readln(st);
      for j:=1 to m do
        a[i,j]:=st[j];
    end;
  xx[1,1]:=1;

  bfs;
  if not fl then
  writeln('No Solution.');

end.