U95041.火烧连营
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
这红莲,为大吴的胜利而绽放!
刘备为报关羽之仇,率70万大军东征孙权,沿长江南岸布下连营七百余里。陆逊观察地形后,决定实施火攻。他将战场抽象为一个 n×m 的网格地图:
每个格子代表一段地形,类型为:
.:平原(可通行,易燃)
T:树林(可通行,极易燃,燃烧速度×2)
R:河流(不可通行,不可燃)
A:刘备军营(起点,火攻目标)
L:陆逊军营(火攻起点)
火攻规则如下:
陆逊在 L 格点燃第一把火。
火势每 1 个单位时间向上下左右四个方向蔓延。
火势蔓延速度:
平原(.):1格/单位时间
树林(T):2格/单位时间(因风助火势,可“跳跃”覆盖相邻两格)
若火势蔓延至 A(刘备军营),则刘备军营立即全军覆没,战役结束。
关键限制:陆逊只能点燃一条连续路径,火势必须沿最短路径传播,且不能绕路。但路径中可包含多个 T,每遇到一个 T,火势会提前 1单位时间到达下一个格子(模拟风向加速)。
现在,曹丕为了做下一步的战略计划,让HQ求出火攻从 L 到达 A 的最短时间。若无法到达,输出 -1。
注意:
T 格子本身不消耗时间(因易燃),但穿过一个 T 会减少后续1单位时间(即“加速”)。
火势在 T 上“跳跃”时,若跳跃后遇到 R,则被阻挡,不能继续。
火势不能穿过 R,也不能重复经过同一格子。
输入格式
第一行:两个整数 n 和 m,表示网格大小
接下来 n 行:每行 m 个字符,表示地图
输出格式
一个整数:火攻到达刘备军营的最短时间(单位:时间步)。若无法到达,输出 -1
输入输出样例
输入#1
5 6 R . . T . . R . T A . . R . . . . . L . . . T . R R R R R .
输出#1
4
说明/提示
1≤n,m≤50
输入解题思路,AI测评打分。不知道怎么写?