1687: [Usaco2005 Open]Navigating the City 城市交通

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 94 Solved: 73
[Submit][Status][Discuss]

Description

由于牛奶市场的需求，奶牛必须前往城市，但是唯一可用的交通工具是出租车．教会奶牛如何在城市里打的．

给出一个城市地图，东西街区E(1≤E≤40)，南北街区N(1≤N≤30).制作一个开车指南给出租车司机，告诉他如何从起点（用S表示）到终点（用E表示）．每一个条目用空格分成两部分，第一个部分是方向（N，E，S，W之一），第二个是一个整数，表示要沿着这个方向开几个十字路口．如果存在多条路线，你应该给出最短的．数据保证，最短的路径存在且唯一．地图中“+”表示十字路口，道路用“I”和“一”表示．建筑和其他设施用“．”表示．下面是一张地图：

出租车可以沿着东，北，西，北，东开两个十字路口，以此类推．具体将由样例给出

Input

第1行：两个用空格隔开的整数N和E.

第2到2N行：每行有2E-I个字符，表示地图．

Output

每行有一个表示方向的字母和一个表示要开几个十字路口的数字表示．

Sample Input

Sample Output

E 1
N 1
W 1
N 1
E 2
S 1
E 3
S 1
W 1

HINT

Source

Silver

题解：一开始没仔细看题的时候以为是灌水法。。。可是后来想到貌似不见得就一条路径，而且题目中貌似说了要最短路径

不知道正解是啥，反正我还是一如既往的逗比——以地图上每个+符号（S、E也算）为节点，建立无向图，然后就成了求最短路径的问题了，然后就是神烦的边spfa边记录路径了，话说这道水题居然写了我好久唉TT

  1 /**************************************************************
  2     Problem: 1687
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:32 ms
  7     Memory:2600 kb
  8 ****************************************************************/
  9  
 10 const dir:array[1..4] of char=('N','E','S','W');
 11 type
 12     point=^node;
 13     node=record
 14                g,w,q:longint;
 15                next:point;
 16     end;
 17 var
 18    i,j,k,l,m,n,x0,y0,x1,y1,x,y,f,r,s,t,v:longint;
 19    map:array[0..100,0..100] of longint;
 20    a:array[0..10000] of point;
 21    b,c,g:array[0..10000] of longint;
 22    d:array[0..100000] of longint;
 23    e,h:array[0..100000,1..2] of longint;
 24    ch:char;
 25    p:point;
 26 procedure add(x,y,z,t:longint);
 27           var p:point;
 28           begin
 29                new(p);p^.g:=y;p^.w:=z;
 30                p^.q:=t;p^.next:=a[x];a[x]:=p;
 31           end;
 32 begin
 33      fillchar(map,sizeof(map),0);
 34      readln(n,m);
 35      n:=n*2-1;m:=m*2-1;
 36      for i:=1 to n do
 37          begin
 38               for j:=1 to m do
 39                   begin
 40                        read(ch);
 41                        case upcase(ch) of
 42                             'S':begin
 43                                      map[i,j]:=-1;
 44                                      x0:=i;y0:=j;
 45                             end;
 46                             'E':begin
 47                                      map[i,j]:=-1;
 48                                      x1:=i;y1:=j;
 49                             end;
 50                             '.':map[i,j]:=0;
 51                             '-':map[i,j]:=-2;
 52                             '|':map[i,j]:=-3;
 53                             '+':map[i,j]:=-1;
 54                        end;
 55                   end;
 56               readln;
 57          end;
 58      s:=0;t:=0;v:=0;
 59      for i:=1 to n do
 60          for j:=1 to m do
 61              if map[i,j]=-1 then
 62                 begin
 63                      inc(v);
 64                      map[i,j]:=v;
 65                      if (x0=i) and (y0=j) then s:=v;
 66                      if (x1=i) and (y1=j) then t:=v;
 67                 end;
 68      for i:=1 to n do
 69          for j:=1 to m do
 70              begin
 71                   if map[i-1,j]<>0 then
 72                      begin
 73                           x:=i-1;y:=j;
 74                           while map[x,y]=-3 do dec(x);
 75                           if map[x,y]>0 then add(map[i,j],map[x,y],1,1);
 76                      end;
 77                   if map[i+1,j]<>0 then
 78                      begin
 79                           x:=i+1;y:=j;
 80                           while map[x,y]=-3 do inc(x);
 81                           if map[x,y]>0 then add(map[i,j],map[x,y],1,3);
 82                      end;
 83                   if map[i,j-1]<>0 then
 84                      begin
 85                           x:=i;y:=j-1;
 86                           while map[x,y]=-2 do dec(y);
 87                           if map[x,y]>0 then add(map[i,j],map[x,y],1,4);
 88                      end;
 89                   if map[i,j+1]<>0 then
 90                      begin
 91                           x:=i;y:=j+1;
 92                           while map[x,y]=-2 do inc(y);
 93                           if map[x,y]>0 then add(map[i,j],map[x,y],1,2);
 94                      end;
 95              end;
 96      fillchar(g,sizeof(g),0);
 97      fillchar(c,sizeof(c),0);
 98      fillchar(b,sizeof(b),0);
 99      fillchar(e,sizeof(e),0);
100      d[1]:=s;f:=1;r:=2;g[s]:=1;c[s]:=1;
101      while f<r do
102            begin
103                 p:=a[d[f]];
104                 while p<>nil do
105                       begin
106                            if (c[p^.g]=0) or ((c[p^.g]>0) and (c[p^.g]>(c[d[f]]+p^.w))) then
107                               begin
108                                    c[p^.g]:=c[d[f]]+p^.w;
109                                    b[p^.g]:=d[f];
110                                    e[p^.g,1]:=p^.q;e[p^.g,2]:=p^.w;
111                                    if g[p^.g]=0 then
112                                       begin
113                                            g[p^.g]:=1;
114                                            d[r]:=p^.g;
115                                            inc(r);
116                                       end;
117                               end;
118                            p:=p^.next;
119                       end;
120                 inc(f);
121                 g[d[f]]:=0;
122            end;
123      for i:=1 to v do dec(c[i]);
124      i:=0;fillchar(h,sizeof(h),0);
125      while t<>0 do
126            begin
127                 inc(i);
128                 h[i,1]:=e[t,1];
129                 h[i,2]:=e[t,2];
130                 t:=b[t];
131            end;
132      v:=i-1;
133      for i:=1 to v div 2 do
134          begin
135               j:=h[i,1];h[i,1]:=h[v+1-i,1];h[v+1-i,1]:=j;
136               j:=h[i,2];h[i,2]:=h[v+1-i,2];h[v+1-i,2]:=j;
137          end;
138      inc(v);h[v,1]:=5;h[v,2]:=0;
139      j:=h[1,1];k:=h[1,2];
140      for i:=2 to v do
141          begin
142               if h[i,1]=j then
143                  k:=k+h[i,2]
144               else
145                   begin
146                        writeln(dir[j],' ',k);
147                        k:=h[i,2];j:=h[i,1];
148                   end;
149          end;
150      readln;
151 end.