USACO OPEN11 Corn Maze

Problem 6: Corn Maze [Sweet Tea Dorminy, 2010]

This past fall, Farmer John took the cows to visit a corn maze. But
this wasn't just any corn maze: it featured several gravity-powered
teleporter slides, which cause cows to teleport instantly from one
point in the maze to another. The slides work in both directions:
a cow can slide from the slide's start to the end instantly, or
from the end to the start. If a cow steps on a space that hosts
either end of a slide, she must use the slide.

The outside of the corn maze is entirely corn except for a single
exit.

The maze can be represented by an N x M (2 <= N <= 300; 2 <= M
<= 300) grid. Each grid element contains one of these items:

   * Corn (corn grid elements are impassable)

   * Grass (easy to pass through!)

   * A slide endpoint (which will transport a cow to the other
     endpoint)

   * The exit

A cow can only move from one space to the next if they are adjacent
and neither contains corn. Each grassy space has four potential
neighbors to which a cow can travel. It takes 1 unit of time to
move from a grassy space to an adjacent space; it takes 0 units of
time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces
are denoted with a period (.). Pairs of slide endpoints are denoted
with the same uppercase letter (A-Z), and no two different slides
have endpoints denoted with the same letter. The exit is denoted
with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her
current grassy space with the 'at' symbol (@). What is the minimum
time she needs to move to the exit space?

Consider the following grid, with N=5 and M=6:

            ###=##
            #.W.##
            #.####
            #.@W##
            ######

A single slide has endpoints denoted by an uppercase W. Her optimal
strategy is to move right to the slide endpoint in 1 time, take the
slide in 0 time to the other endpoint, and move right and up in 2
more time to end on the exit.  This requires a total of 3 time, the
minimum.

PROBLEM NAME: cornmaze

INPUT FORMAT:

* Line 1: Two space separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the maze: M characters (no
        spaces)

SAMPLE INPUT (file cornmaze.in):

5 6
###=##
#.W.##
#.####
#.@W##
######

OUTPUT FORMAT:

* Line 1: An integer, corresponding to the shortest time that Bessie
        needs to exit the maze.

SAMPLE OUTPUT (file cornmaze.out):

3

===================================================================

本题的关键在于构图，本人先对每个点标号，然后建立一张加权图。
还需要注意到的是，一旦到达某个传送点，就会立即转移到另一个出口。因此我把每个传送点拆成两个点，一个流入，另一个流出，并且在这一侧的流入和另一侧的流出点间建立一条边。
最后，SPFA计算从@点到=点的最短路即可。（最大点数有90000,朴素Dijstra不能承受）

C语言: 高亮代码由发芽网提供

001 #include
002 #include
003 #include
004 #define MAXN 302
005 #define INF 1000000000
006
007 int dx[4] = {0,0,-1,1};
008 int dy[4] = {1,-1,0,0};
009
010 typedef struct node
011 {
012    struct node *next;
013    short w;
014    long v;
015 }node;
016
017 node *first[MAXN * MAXN];
018
019 char map[MAXN][MAXN];
020 long in[MAXN][MAXN],out[MAXN][MAXN];
021 int M,N;
022 long dist[MAXN * MAXN];
023 long tot = 0;
024 long S,T;
025
026 inline void addedge(long a,long b,short c)
027 {
028    node *p = malloc(sizeof(node));
029    p->v = b;
030    p->w = c;
031    p->next = first[a];
032    first[a] = p;
033 }
034
035 void init()
036 {
037    int i,j,k;
038    int pos[28][2][2] = {};
039    int vis[28] = {};
040    scanf("%d%d\n",&N,&M);
041    for(i = 1;i <= N;i ++)
042    {
043        scanf("%s\n",&map[i][1]);
044        for(j = 1;j <= M;j ++)    //标号
045        {
046            if(map[i][j] == '#')    continue;
047            in[i][j] = out[i][j] = ++tot;
048            if(map[i][j] == '@')    S = out[i][j];
049            else if(map[i][j] == '=')    T = in[i][j];
050            else if(map[i][j] <= 'Z' && map[i][j] >= 'A')    //拆开传送点
051                out[i][j] = ++tot;
052        }
053    }
054    for(i = 1;i <= N;i ++)     //建图
055        for(j = 1;j <= M;j ++)
056        {
057            if(map[i][j] != '#')
058            {
059                for(k = 0;k < 4;k ++)
060                    if(map[i + dx[k]][j + dy[k]] != '#')    addedge(out[i][j],in[i + dx[k]][j + dy[k]],1);
061                if(map[i][j] <= 'Z' && map[i][j] >= 'A')
062                {
063                    if(!vis[map[i][j] - 'A'])
064                    {
065                        vis[map[i][j] - 'A'] = 1;
066                        pos[map[i][j] - 'A'][0][0] = i;
067                        pos[map[i][j] - 'A'][0][1] = j;
068                    }
069                    else
070                    {
071                        pos[map[i][j] - 'A'][1][0] = i;
072                        pos[map[i][j] - 'A'][1][1] = j;
073                    }
074                }
075            }
076        }
077    for(i = 0;i < 28;i ++)
078        if(vis[i])
079        {
080            addedge(in[pos[i][0][0]][pos[i][0][1]],out[pos[i][1][0]][pos[i][1][1]],0);
081            addedge(in[pos[i][1][0]][pos[i][1][1]],out[pos[i][0][0]][pos[i][0][1]],0);
082        }
083 }
084
085 long Q[MAXN * MAXN * 10],head,tail;
086
087 inline void enq(long x)
088 {
089    Q[tail ++] = x;
090 }
091
092 inline long deq()
093 {
094    return Q[head ++];
095 }
096
097 void SPFA()
098 {
099    long i;
100    node *p;
101    for(i = 1;i <= tot;i ++)
102        dist[i] = INF;
103    dist[S] = 0;
104    enq(S);
105    while(head < tail)
106    {
107        i = deq();
108        for(p = first[i];p != NULL;p = p->next)
109            if(dist[p->v] > dist[i] + p->w)
110            {
111                dist[p->v] = dist[i] + p->w;
112                enq(p->v);
113            }
114    }
115    printf("%ld\n",dist[T]);
116 }
117
118 int main()
119 {
120    freopen("cornmaze.in","r",stdin);
121    freopen("cornmaze.out","w",stdout);
122    init();
123    SPFA();
124    fclose(stdout);
125    return 0;
126 }