U95041.火烧连营

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

这红莲,为大吴的胜利而绽放!

刘备为报关羽之仇,率70万大军东征孙权,沿长江南岸布下连营七百余里。陆逊观察地形后,决定实施火攻。他将战场抽象为一个 ‌n×mn×m 的网格地图‌:
每个格子代表一段地形,类型为:
.:平原(可通行,易燃)
T:树林(可通行,极易燃,燃烧速度×2)
R:河流(不可通行,不可燃)
A:刘备军营(起点,火攻目标)
L:陆逊军营(火攻起点)
火攻规则如下:

陆逊在 L 格点燃第一把火。
火势每‌ 11 个单位时间‌向‌上下左右‌四个方向蔓延。
火势蔓延速度:
平原(.):11格/单位时间
树林(T):22格/单位时间(因风助火势,可“跳跃”覆盖相邻两格)
若火势蔓延至 A(刘备军营),则刘备军营‌立即全军覆没‌,战役结束。
‌关键限制‌:陆逊只能点燃‌一条连续路径‌,火势必须沿‌最短路径‌传播,且不能绕路。但路径中可包含多个 T,每遇到一个 T,火势会‌提前 11单位时间‌到达下一个格子(模拟风向加速)。
‌现在,曹丕为了做下一步的战略计划,让HQHQ求出火攻从 L 到达 A 的‌最短时间‌。若无法到达,输出 -1
注意‌:

T 格子本身不消耗时间(因易燃),但‌穿过一个 T 会减少后续1单位时间‌(即“加速”)。
火势在 T 上“跳跃”时,若跳跃后遇到 R,则被阻挡,不能继续。
火势不能穿过 R,也不能重复经过同一格子。

输入格式

第一行:两个整数 nnmm,表示网格大小
接下来 nn 行:每行 mm 个字符,表示地图

输出格式

一个整数:火攻到达刘备军营的最短时间(单位:时间步)。若无法到达,输出 -1

输入输出样例

  • 输入#1

    5 6
    R . . T . .
    R . T A . .
    R . . . . .
    L . . . T .
    R R R R R .
    

    输出#1

    4

说明/提示

1n,m501 \le n,m \le 50

输入解题思路,AI测评打分。不知道怎么写?

首页