hdu Magic maze bfs+優先隊列 解題報告

Problem Description   天外來客 likes playing computer game very much. Recently, he is playing a RPG game called “仙劍奇俠傳4”. But when he was playing the game, he meets a very mad problem. There are so many mazes in the game and CHN was not good at passing the mazes. So he is very unhappy these days. Can you help him?

  Here is a magic maze. When one person stands on a position(x0, y0), he can choose to jump to the other one position(x1, y1), which has a relation with the position(x0, y0). One position can have only one relation. One person can move left, right, up or down. One move or one jump will take one minute.

  There are only have ‘.’ or ‘#’, ’S’, ’E’ on the map of the magic maze. ’.’ indicates the blank which person can move on, ‘#’ indicates wall. Maybe a blank have relation of a wall. ’S’ indicates the entrance location. ‘E’ indicates the exit location . There is only one ‘S’ and one ‘E’.

  Input   The first line is an integer t, which means the number of test case in the data file. For each test case, the first line consist of two integer r (2<=r<=20) and c (2<=c<20), which mean the number of rows or columns. The next r line is the map’s description; each line consists of c letters. The next line is an integer k (0<=k<=(r*c)/2), which mean the relations of two position. The next k lines, each line consist of four integers x1, y1, x2, y2, which means (x1,y1) has a relation with (x2, y2) and (x2, y2) also has a relation with (x1, y1).

(0<=x1,x2=<r-1,0<=y1,y2<=c-1)

You can jump from one position to another.

  Output   For each test case, you only outputs the Minimum time that one person will take from the entrance location to the exit location. If he can’t find the exit position, you must output ‘-1’.

  SampleInput

1
6 6
S..#..
...#..
...#..
.#.#..
...#.#
.....E
3
1 2 4 4
0 1 4 5
0 0 4 2      

  SampleOutput

5      

  分析：注意初始化，其他基本都是套路。

代碼：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int n,m,sx,sy,num,a,b,c,d;
char map[50][50];
int fx[4][2]={0,1,1,0,0,-1,-1,0};
int vis[50][50];
struct fei
{
    int x,y;
    fei(){x=-1;y=-1;}
}f[50][50];

struct node
{
    int x,y,step;
    friend bool operator<(node n1,node n2)
    {
        return n1.step>n2.step;
    }
}t,p;

int bfs()
{
    priority_queue<node> Q;
    t.x=sx;
    t.y=sy;
    t.step=0;
    Q.push(t);
    while(!Q.empty())
    {
        t=Q.top();
        Q.pop();
        if(map[t.x][t.y]=='E') return t.step;

        //先處理可以跳的
        if(f[t.x][t.y].x!=-1)
        {
            p.x=f[t.x][t.y].x;
            p.y=f[t.x][t.y].y;
            p.step=t.step+1;
            if(p.x>=0&&p.x<n&&p.y>=0&&p.y<m&&!vis[p.x][p.y])
            {
                if(map[p.x][p.y]=='.'||map[p.x][p.y]=='E')
                {
                    Q.push(p);
                    vis[p.x][p.y]=1;
                }
            }
        }
        for(int i=0;i<4;i++)
        {
            p.x=t.x+fx[i][0];
            p.y=t.y+fx[i][1];
            p.step=t.step+1;
            if(p.x>=0&&p.x<n&&p.y>=0&&p.y<m&&!vis[p.x][p.y])
            {
                if(map[p.x][p.y]=='.'||map[p.x][p.y]=='E')
                {
                    Q.push(p);
                    vis[p.x][p.y]=1;
                }
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //初始化
        for(int i=0;i<50;i++)
            for(int j=0;j<50;j++)
                f[i][j].x=-1,f[i][j].y=-1;
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%s",map[i]);
            for(int j=0;map[i][j];j++)
            {
                if(map[i][j]=='S'){sx=i;sy=j;}
            }
        }
        scanf("%d",&num);
        for(int i=0;i<num;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            f[a][b].x=c;
            f[a][b].y=d;
            f[c][d].x=a;
            f[c][d].y=b;
        }
        printf("%d\n",bfs());
    }
    return 0;
}