team2012-D1-sol-0013

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
给出一个 n * m 的格子图, 有些格子不能走, 有些格子上有守护者(也不能走). 守护者每一个时刻会朝着上下左右其中一个方向, 如果你在这一秒走到他的视野内, 他就会过来跟你打一架, 而且你肯定会打败他, 但是打败之后他不会消失. 每过一秒守护者会顺时针转90度. 你每秒可以朝上下左右走一格, 不可以停留. 现在你在 (Xs, Ys), 问到 (Xt, Yt) 需要最少打多少架, 在打架数最少的前提下, 使路径尽可能短.

=== 数据范围 ===
 * 2 ≤ n ≤ 100
 * 2 ≤ m ≤ 100
 * 0 ≤ s ≤ n * m
 * 1 ≤ ri ≤ 100

=== 解题思路 ===
首先, 这一秒的地图和上一秒是不一样的, 因为守护者的视线会变; 同时注意到也只有这一点使得地图信息每一秒不一样, 因为守护者每过 4 秒就会回到之前的位置, 所以一共只会有 4 张不同的地图. 分成 4 层图之后, 做一次双关键字的 SPFA 即可. 一开始直接 flood-fill 我真是太 naive 了 233.

题目大意

给出一个 n * m 的格子图, 有些格子不能走, 有些格子上有守护者(也不能走). 守护者每一个时刻会朝着上下左右其中一个方向, 如果你在这一秒走到他的视野内, 他就会过来跟你打一架, 而且你肯定会打败他, 但是打败之后他不会消失. 每过一秒守护者会顺时针转90度. 你每秒可以朝上下左右走一格, 不可以停留. 现在你在 (Xs, Ys), 问到 (Xt, Yt) 需要最少打多少架, 在打架数最少的前提下, 使路径尽可能短.

数据范围

• 2 ≤ n ≤ 100
• 2 ≤ m ≤ 100
• 0 ≤ s ≤ n * m
• 1 ≤ ri ≤ 100

解题思路

首先, 这一秒的地图和上一秒是不一样的, 因为守护者的视线会变; 同时注意到也只有这一点使得地图信息每一秒不一样, 因为守护者每过 4 秒就会回到之前的位置, 所以一共只会有 4 张不同的地图. 分成 4 层图之后, 做一次双关键字的 SPFA 即可. 一开始直接 flood-fill 我真是太 naive 了 233.