游客 注册 | 登录
中文 | En

3012 - 小俞同学的危机

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

最近小俞同学学习真是太累了，不知不觉就趴在桌子上睡着了。她进入了一个奇怪的梦境，梦到进入了一个迷宫里，这下可愁坏了小俞，最近没吃饱，走也走不动了，只能困在迷宫里面动不了。幸运的是她在梦里梦见了你也在迷宫里，你手里还有一些好吃的，把这些好吃的给她，她就能和你一起跑出去啦。不过迷宫里面有一些大恶魔在，还好你有足够的力量消灭它，但是消灭它也需要一些时间的。好吧，地图给你了，现在快去营救机房女神吧！！

地图是一个四方的地图，你只能从一个格子从上、下、左、右、四个方向走到另一个临近的格子里面，并且花费1个时间单位，消灭恶魔也需要一个单位，有恶魔在的格子，只有消灭了恶魔，才能通行。

题目输入

第一行N和M代表N行M列（1<=N<=200, 1<=M<=200）

接下来N行，没行M个字符，每个字符之间没有空格，整个输入保证没有多余不可见字符。

‘a’代表小俞同学的所在地，‘r'代表你的起始位置，’x'代表恶魔，’#'是墙，'.'代表道路。


题目输出

每组测试样例，输出一个整数，表示从出发到接到小俞同学的步数。由于小俞同学非常的害怕和饿（主要是饿），你要不是用最少的步数到达她身边的话，她就会不高兴，而且最重要的是她不跟你走！！！这样她就永远的困在梦境里面了。。。。。（你的任务也失败了）好惨

不过如果你根本到达不了她身边的话，就输出“I'm so sorry, but I can fly! bye~”（输出不带引号）。

输入/输出样例

输入格式

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

输出格式

13

C语言解答

#include<stdio.h>
#include<string.h>
char a[202][202];
int b[202][202];
int n,m,sum;
void dfs(int x,int y,int t)
{
    if(a[x][y]=='a'&&t<sum)
        sum=t;
    if(!b[x][y]&&a[x][y]!='#'&&x-1>=0)
    {
        b[x][y]=1;
        if(a[x][y]=='x')
        dfs(x-1,y,t+2);
        else dfs(x-1,y,t+1);
        b[x][y]=0;

    }
    if(!b[x][y]&&a[x][y]!='#'&&x+1<n)
    {
        b[x][y]=1;
        if(a[x][y]=='x')
        dfs(x+1,y,t+2);
        else dfs(x+1,y,t+1);
        b[x][y]=0;

    }
    if(!b[x][y]&&a[x][y]!='#'&&y-1>=0)
    {
        b[x][y]=1;
        if(a[x][y]=='x')
        dfs(x,y-1,t+2);
        else dfs(x,y-1,t+1);
        b[x][y]=0;

    }
    if(!b[x][y]&&a[x][y]!='#'&&y+1<m)
    {
        b[x][y]=1;
        if(a[x][y]=='x')
        dfs(x,y+1,t+2);
        else dfs(x,y+1,t+1);
        b[x][y]=0;
    }
}
int main()
{
    int i,j,x1,x2,y1,y2;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        getchar();
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j]=='r') x1=i,y1=j;
                if(a[i][j]=='a') x2=i,y2=j;
            }
            getchar();
        }
        memset(b,0,sizeof(b));
        sum=999999;
        dfs(x1,y1,0);
        if(sum==999999) printf("I'm so sorry, but I can fly! bye~\n");
        else printf("%d\n",sum);
    }
    return 0;
}

C++解答

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

int n, m;
char mp[205][205];
bool v[205][205];
int mv[4][2] =
{
    1, 0,
    0, 1,
    0, -1,
    -1, 0
};

struct Node
{
    int x;
    int y;
    int tep;
    Node(int tx, int ty, int tep)
    {
        x = tx;
        y = ty;
        this -> tep = tep;
    }
    Node(){}
};

int bfs(int sx, int sy)
{
    queue<Node> Q;
    Node node(sx, sy, 0);
    Node temp;
    Q.push(node);
    int x, y, tep;
    while(!Q.empty())
    {
        temp = Q.front();
        Q.pop();
        x = temp.x;
        y = temp.y;
        tep = temp.tep;
//        printf("x = %d y = %d tep = %d\n", x, y, tep);
        if(mp[x][y] == 'a')
        {
            return tep;
        }
        if(mp[x][y] == 'x')
        {
            mp[x][y] = '.';
            Node p(x, y, tep + 1);
            Q.push(p);
            continue;
        }
        for(int i = 0; i < 4; i++)
        {
            int tx = x + mv[i][0];
            int ty = y + mv[i][1];
            if(tx <0 || ty < 0 || tx >= n || ty >= m)
            {
                continue;
            }
            if(!v[tx][ty] && mp[tx][ty] != '#')
            {
                v[tx][ty] = true;
                Node p(tx, ty, tep + 1);
                Q.push(p);
            }
        }
    }
    return 0;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    while(cin >> n >> m)
    {
        int sx, sy;
        memset(v, false, sizeof(v));
        for(int i = 0; i < n; i++)
        {
            for(int k = 0; k < m; k++)
            {
                cin >> mp[i][k];
                if(mp[i][k] == 'r')
                {
                    sx= i;
                    sy = k;
                }
            }
        }
        int t = bfs(sx, sy);
        if(t)
        {
            printf("%d\n", t);
        }
        else
        {
            printf("I'm so sorry, but I can fly! bye~\n");
        }
    }
    return 0;
}
请先登陆