小乐乐打游戏（BFS+曼哈顿距离）

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。

最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。

吃猪游戏很简单，给定一个地图，大小为n*m，在地图中会随机出现一个火山口，只要小乐乐能逃离这个地图，他便能吃猪！

但吃鸡远没有那么简单：

        1.小乐乐每走一次只能上下左右四个方向中走一步。

        2.小乐乐每走一步，火山喷发的岩浆就会向四周蔓延一个格子，所有岩浆走过的地方都视为被岩浆覆盖。

        3.小乐乐碰到岩浆就会死。

        4.地图中还有很多障碍，使得小乐乐不能到达，但是岩浆却可以把障碍融化。

        5.小乐乐只有走到题目给定的终点才算游戏胜利，才能吃猪。

小乐乐哪见过这场面，当场就蒙了，就想请帮帮他，告诉他是否能吃猪。

输入描述:

多组样例输入

第一行给定n,m,(1 <= n, m <= 1000)代表地图的大小。

接下来n行，每一行m个字符，代表地图，对于每一个字符，如果是'.'，代表是平地，'S'代表小乐乐起始的位置，

'E'代表终点，'#'代表障碍物，'F'代表火山口。

输出描述:

输出只有一行。如果小乐乐能吃猪，输出"PIG PIG PIG!"。否则输出"A! WO SI LA!"。

示例1

输入

复制

3 3

F..

#S#

#.E

输出

复制

PIG PIG PIG!

代码：

#include <cstdlib>

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48,ch=getchar();}

    return x*f;

}

const int maxn = 1010;

char s[maxn][maxn];

struct edge{

    int to,next;

}e[maxn*maxn*2];

int tot,head[maxn*maxn];

void add(int u,int v){

    e[++tot].to=v;

    e[tot].next=head[u];

    head[u]=tot;

}

int dis[maxn*maxn],num[maxn][maxn],S,T,Fx,Fy;

int tim[maxn*maxn];

int dx[]={0,1,-1,0,0};

int dy[]={0,0,0,1,-1};

int main()

{

    int n,m,cnt=0;

    while(scanf("%d%d",&n,&m)!=EOF){

        cnt=0,tot=0;

        memset(head,0,sizeof head);

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

            scanf("%s",s[i]+1);

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

                num[i][j]=++cnt;

                if(s[i][j]=='S') S=cnt;

                if(s[i][j]=='E') T=cnt;

                if(s[i][j]=='F') Fx=i,Fy=j;

            }

        }

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

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

                tim[num[i][j]]=abs(Fx-i)+abs(Fy-j);

                if(s[i][j]=='#')continue;

                for(int k=1;k<=4;k++){

                    int x=i+dx[k],y=j+dy[k];

                    if(x<=0||y<=0||x>n||y>m||s[x][y]=='#')continue;

                    add(num[i][j],num[x][y]);

                }

            }

        }

        queue<int>q;

        memset(dis,0x3f,sizeof dis);

        q.push(S);dis[S]=0;

        while(!q.empty()){

            int x=q.front();q.pop();

            for(int i=head[x];i;i=e[i].next){

                int to=e[i].to;

                if(dis[x]+1>=tim[to]) continue;

                if(dis[to]>dis[x]+1){

                    q.push(to);dis[to]=dis[x]+1;

                }

            }

        }

        if(dis[T]==0x3f3f3f3f) printf("A! WO SI LA!\n");

        else printf("PIG PIG PIG!\n");

    }

}

巴特西

小乐乐打游戏（BFS+曼哈顿距离）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章