295B

题目链接：https://codeforces.com/problemset/problem/295/B 题目描述可参见 洛谷 解题思路完全来自 aiiYuu巨佬的博客 一道很好地利用了 floyd 算法性质的题目。 floyd算法 示例程序： #include <bits/stdc++.h> us ......

# Floyd 原理简析 Floyd 的原理其实是 DP，定义 $\mathrm{dp}[S][i][j]$ 表示在仅经过点集 $S$ 里的点的条件下，从 $i$ 到 $j$ 的最短路距离 初始状态 $S$ 为空，$\mathrm{dp}[\varnothing ][i][j]$ 就等于 $i,j$ ......

题目大意： 给出一张地图，其中 # 表示障碍物，如果某个位置上有数字，就表示这个位置上有一个范围为这个数字的炸弹。在这个炸弹范围内的所有格子都要变为 .。问我们最后的地图是怎样的。 解题思路： 因为这里的距离是曼哈顿距离，所以我们可以以一个炸弹为中心，在这个距离内跑一遍深搜，把遍历到的格子改成 .。 ......