2018年湘潭大学程序设计竞赛 maze(bfs)

时间：2023-03-10 08:05:18
2018年湘潭大学程序设计竞赛 maze(bfs)

链接：https://www.nowcoder.com/acm/contest/105/F
来源：牛客网

有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

输入描述:

有多组数据。对于每组数据：
第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。
最后q行，每行四个整数

2018年湘潭大学程序设计竞赛 maze(bfs)

表示一个传送阵的入口在x

1

行y

1

列，出口在x

2

行y

2

列。


输出描述:


如果小明能够活着到达目的地，则输出最短时间，否则输出-1。




示例1






输入




5 5 1

..S..

.....

.###.

.....

..T..

1 2 3 3

5 5 1

..S..

.....

.###.

.....

..T..

3 3 1 2

5 5 1

S.#..

..#..

###..

.....

....T

0 1 0 2

4 4 2

S#.T

.#.#

.#.#

.#.#

0 0 0 3

2 0 2 2








输出




6

8

-1

3
bfs,注意，可能通过不止一个传送阵




#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

typedef long long ll;

struct node

{

    int x,y,step;

    node(int x=,int y=,int t=):x(x),y(y),step(step){};

    bool operator<(const node a) const

    {

        return a.step<step;

    }

}ans,pos;

int dir[][]={{,},{,},{,-},{-,}};

int n,m,k,xs,ys;

int dis[][];

char a[][];

int xa,xb,ya,yb;

vector<node>vis[][];

int bfs(int u,int v)

{

    priority_queue<node>q;

    memset(dis,INF,sizeof(dis));

    ans.x=u;ans.y=v;

    ans.step=;

    dis[u][v]=;

    q.push(ans);

    while(!q.empty())

    {

        pos=q.top();

        q.pop();

        if(a[pos.x][pos.y]=='T') return pos.step;

        for(int i=;i<vis[pos.x][pos.y].size();i++)

        {

            ans=vis[pos.x][pos.y][i];

            if(dis[ans.x][ans.y]>pos.step+)

            {

                ans.step=pos.step+;

                dis[ans.x][ans.y]=pos.step+;

                q.push(ans);

            }

        }

        for(int i=;i<;i++)

        {

            ans.x=pos.x+dir[i][];

            ans.y=pos.y+dir[i][];

            ans.step=pos.step+;

            if(ans.x>= && ans.x<n && ans.y>= && ans.y<m && a[ans.x][ans.y]!='#' && dis[ans.x][ans.y]>ans.step)

            {

                dis[ans.x][ans.y]=pos.step+;

                q.push(ans);

            }

        }

    }

    return -;

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        for(int i=;i<n;i++)

        {

            scanf("%s",&a[i]);

            for(int j=;j<m;j++)

            {

                vis[i][j].clear();

                if(a[i][j]=='S') xs=i,ys=j;

            }

        }

        for(int i=;i<k;i++)

        {

            scanf("%d%d%d%d",&xa,&ya,&xb,&yb);

            if(a[xa][ya]!='#' && a[xb][yb]!='#')

                vis[xa][ya].push_back(node(xb,yb));

        }

        int cnt=bfs(xs,ys);

        printf("%d\n",cnt);

    }

    return ;

}#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

typedef long long ll;

struct node

{

    int x,y,step;

    node(int x=,int y=,int t=):x(x),y(y),step(step){};

    bool operator<(const node a) const

    {

        return a.step<step;

    }

}ans,pos;

int dir[][]={{,},{,},{,-},{-,}};

int n,m,k,xs,ys;

int dis[][];

char a[][];

int xa,xb,ya,yb;

vector<node>vis[][];

int bfs(int u,int v)

{

    priority_queue<node>q;

    memset(dis,INF,sizeof(dis));

    ans.x=u;ans.y=v;

    ans.step=;

    dis[u][v]=;

    q.push(ans);

    while(!q.empty())

    {

        pos=q.top();

        q.pop();

        if(a[pos.x][pos.y]=='T') return pos.step;

        for(int i=;i<vis[pos.x][pos.y].size();i++)

        {

            ans=vis[pos.x][pos.y][i];

            if(dis[ans.x][ans.y]>pos.step+)

            {

                ans.step=pos.step+;

                dis[ans.x][ans.y]=pos.step+;

                q.push(ans);

            }

        }

        for(int i=;i<;i++)

        {

            ans.x=pos.x+dir[i][];

            ans.y=pos.y+dir[i][];

            ans.step=pos.step+;

            if(ans.x>= && ans.x<n && ans.y>= && ans.y<m && a[ans.x][ans.y]!='#' && dis[ans.x][ans.y]>ans.step)

            {

                dis[ans.x][ans.y]=pos.step+;

                q.push(ans);

            }

        }

    }

    return -;

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        for(int i=;i<n;i++)

        {

            scanf("%s",&a[i]);

            for(int j=;j<m;j++)

            {

                vis[i][j].clear();

                if(a[i][j]=='S') xs=i,ys=j;

            }

        }

        for(int i=;i<k;i++)

        {

            scanf("%d%d%d%d",&xa,&ya,&xb,&yb);

            if(a[xa][ya]!='#' && a[xb][yb]!='#')

                vis[xa][ya].push_back(node(xb,yb));

        }

        int cnt=bfs(xs,ys);

        printf("%d\n",cnt);

    }

    return ;

}










相关文章