2017哈理工低年级组院赛初赛 D-逃脱 【一个贼墨迹的bfs】

原创 2017年12月13日 19:56:48
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

 这是mengxiang000和Tabris来到幼儿园的第四天,幼儿园老师在值班的时候突然发现幼儿园某处发生火灾,而且火势蔓延极快,老师在第一时间就发出了警报,位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑,不知道两人是否能够逃脱险境?

幼儿园可以看成是一个N*M的图,在图中一共包含以下几种元素:

“.”:表示这是一块空地,是可以随意穿梭的。

“#”:表示这是一块墙,是不可以走到这上边来的,但是可以被火烧毁。

“S”:表示mengxiang000和Tabris所在位子。

“E”:表示幼儿园的出口。

“*”表示火灾发源地(保证输入只有一个火灾发源地)。

已知每秒有火的地方都会向周围八个格子(上下左右、左上、右上、左下、右下)蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子(上下左右)进行移动。(假设两人这一秒行动完之后,火势才蔓延开)

根据已知条件,判断两人能否成功逃脱险境,如果可以,输出最短逃离时间,否则输出T_T。

输入描述:

第一行输入一个整数t,表示一共的测试数据组数。
第二行输入两个整数n,m,表示幼儿园的大小。
接下来n行,每行m个字符,表示此格子是什么元素。
t<=200
3<=n<=30
3<=M<=30
保证图中有一个起点,一个出口,一个火灾源处.
为了防止孩子们嬉戏中受伤,墙体是橡胶制作的,可以燃烧的哦。

输出描述:

每组数据输出一行,如果两人能够成功到达出口,那么输出最短逃离时间,否则输出T_T
示例1

输入

3
5 5
*....
.....
..S#.
...E.
.....
5 5
...#*
..#S#
...##
....E
.....
5 5
.....
S....
..*#.
...E.
.....

输出

2
T_T
T_T

说明

为了防止孩子们嬉戏中受伤,墙体是橡胶制作的,可以燃烧的哦。

无亮点,就是墨迹;


#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x, y, step;
};
int n, m;
char maps[35][35];
int fire[35][35];
int vis[35][35];
int step[4][2]= {1, 0, 0, 1, -1, 0, 0, -1};
int step_fire[8][2]= {1, 0, 0, 1, -1, 0, 0, -1, 1, -1, -1, 1, 1, 1, -1, -1};
void bfs_fire(int sx, int sy)
{
    memset(vis, 0, sizeof vis);
    memset(fire, 0, sizeof fire);
    vis[sx][sy] = 1;
    node op, uv;
    op.x = sx;
    op.y = sy;
    op.step = 0;
    queue<node >q;
    q.push(op);
    while(!q.empty())
    {
        op=q.front();
        q.pop();
        for(int i = 0; i < 8; i++)
        {
            uv.x = op.x + step_fire[i][0];
            uv.y = op.y + step_fire[i][1];
            if(uv.x >= 0 && uv.x < n && uv.y >= 0
                    && uv.y < m && vis[uv.x][uv.y] == 0)
            {
                fire[uv.x][uv.y] = op.step + 1;
                vis[uv.x][uv.y] = 1;
                uv.step = op.step + 1;
                q.push(uv);
            }
        }
    }
}

void bfs(int sx, int sy)
{
    memset(vis, 0, sizeof vis);
    vis[sx][sy] = 1;
    node fr,ne;
    fr.x = sx;
    fr.y = sy;
    fr.step = 0;
    queue<node >q;
    q.push(fr);
    while(!q.empty())
    {
        fr = q.front();
        if(maps[fr.x][fr.y] == 'E')
        {
            cout << fr.step << endl;
            return;
        }
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            ne.x = fr.x + step[i][0];
            ne.y = fr.y + step[i][1];
            ne.step = fr.step + 1;
            if(ne.x >= 0 && ne.x < n && ne.y >= 0 && ne.y < m
                    && vis[ne.x][ne.y] == 0
                    && ne.step < fire[ne.x][ne.y] 
                    && maps[ne.x][ne.y] != '#')
            {
                vis[ne.x][ne.y] = 1;
                q.push(ne);
            }
            if(ne.x >= 0 && ne.x < n && ne.y >= 0
                    && ne.y < m && vis[ne.x][ne.y] == 0
                    && ne.step == fire[ne.x][ne.y] 
                    && maps[ne.x][ne.y] == 'E')
            {
                vis[ne.x][ne.y] = 1;
                q.push(ne);
            }
        }
    }
    cout << "T_T" << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        int x, y, x_fire, y_fire;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", maps[i]);
            for(int j = 0; j < m; j++)
            {
                if(maps[i][j] == 'S')
                {
                    x = i;
                    y = j;
                }
                else if(maps[i][j] == '*')
                {
                    x_fire = i;
                    y_fire = j;
                }
            }
        }
        bfs_fire(x_fire, y_fire);
        bfs(x, y);
    }
    return 0;
}

2017 哈理工低年级组院赛初赛 H-魔法阵 【规律】

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld 题目描述  这是mengxian...
  • Head_Hard
  • Head_Hard
  • 2017年12月12日 21:33
  • 51

哈理工软件学院"兆方美迪"杯第六届程序设计大赛【高年级组】--决赛 Problem D: 经商 By Assassin

Description小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段,当然人际关系是需要放在首位的。小d每一个月都需要列出来一个人际关系表,表示他们搞房地产的人的一个人际关系网,但是他的精力...
  • qq_35078631
  • qq_35078631
  • 2016年11月21日 10:51
  • 331

2017哈理工 低年级组院赛初赛 G-做游戏 【水题】

题目描述 今天是Tabris和mengxiang000来到幼儿园的第9天。 为了庆祝这美好的一天,老师组织同学们做游戏,拿来了好多骰子。 游戏规则: 1)两个人每人轮流掷骰子,...
  • Head_Hard
  • Head_Hard
  • 2017年12月11日 17:26
  • 36

浅谈2017noip信息奥赛普及组试题

一些日常刷题策略(转载):下面就是进入正题了(其实这也是我第一次在csdn写博客,所以写的不好的地方也请大家多多谅解和提点微笑)一、score 成绩 (本文题目信息皆来自洛谷) 【题目描述】牛牛最...
  • qq_35416331
  • qq_35416331
  • 2017年11月27日 23:38
  • 141

2017湖湘杯网络安全大赛Writeup

大赛分为初赛、复赛、决赛。 初赛150道理论题,前300名进入复赛,复赛为夺旗赛(CTF)竞赛模式。 湖湘杯网络安全大赛相关链接:【传送门】 复赛为web渗透,反编译,破解,加密&解密 一共15道...
  • qq_27446553
  • qq_27446553
  • 2017年12月15日 09:36
  • 265

2017广东工业大学ACM新生杯初赛

真想再体验一把新生杯。(部分题解) Problem A: Chinese Remainder Theorem 思路:中国剩余定理,套个板子就行了,注意输入的数据要去重。 # include ...
  • junior19
  • junior19
  • 2017年12月02日 17:23
  • 231

bfs 思路 hrbust院赛初赛D

逃脱 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld 题目描述  这是mengxian...
  • qq_40999273
  • qq_40999273
  • 2017年12月14日 16:37
  • 28

浙江理工大学zstu2016新生赛题解

A:Save the Princess 题目:点击打开链接 题意:n个人横向排好队,其中左数第k个是公主,LYF和BH分别可以杀掉队列最左边的或者最右边的人,直到某个人拯救公主,两个人都会选择最佳杀人...
  • pan1197349032
  • pan1197349032
  • 2016年11月21日 17:37
  • 1566

2017年蓝桥杯省赛自白

今年的蓝桥省赛,的确有些出人意料,题目难度一下子提升了,倒不是说特别的难,只是让我十分不适应,同样报名的 A 组,去年却水的轻松过线,经过一年的准备,这次却挂了~~~这次没有过线,也是在我意料之中,和...
  • f_zyj
  • f_zyj
  • 2017年04月13日 17:37
  • 3483

哈尔滨理工大学第七届程序设计竞赛决赛(网络赛-高年级组)- (A,B)

比赛AC了A,B题后,看了看D也没思路就没再做,A题n明明达到1e3我还先dfs了一下,其实是个简单dp,这个B题可以说是把基本错误犯了个遍,思路一直是对的,WA了8次才A, A...
  • sdau20163942
  • sdau20163942
  • 2017年12月10日 17:25
  • 86
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:2017哈理工低年级组院赛初赛 D-逃脱 【一个贼墨迹的bfs】
举报原因:
原因补充:

(最多只允许输入30个字)