team2012-D1-sol-0042

从 Trac 迁移的文章

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

原文章内容如下：

一道很普通的格子题, 先预处理出来每个格子会受到的伤害. 注意到虽然 q 的范围比较大, 但 p 的范围很小, 所以可以按照枚举每种伤害来做, 时间复杂度乘以 7 而已. 做的时候将四个方向分开来做, 就可以 O(N*M) 的搞定每个方向. 预处理是 O(Pmax*N*M) 的. 然后就是一个裸的分层图 bfs 了. f[i][j][k] 表示 "在 (j, k) 点且受到电击后血量为 i 所需的最少回合数".

一道很普通的格子题, 先预处理出来每个格子会受到的伤害. 注意到虽然 q 的范围比较大, 但 p 的范围很小, 所以可以按照枚举每种伤害来做, 时间复杂度乘以 7 而已. 做的时候将四个方向分开来做, 就可以 O(N*M) 的搞定每个方向. 预处理是 O(Pmax*N*M) 的. 然后就是一个裸的分层图 bfs 了. f[i][j][k] 表示 "在 (j, k) 点且受到电击后血量为 i 所需的最少回合数".