Stealing Harry Potter’s Precious
题意：给一个n * m的图，图上每一个点要么是’.’，要么是’@’，要么是’#’。’@‘表示起点，’.‘表示必经点，’#‘表示障碍点。规定从起点出发，每一步只能向上、下、左、或右走出一步，问至少经过多少步，可以在不经过障碍的情况下，使得’.'至少经过一次
思路：由于这道题目数据范围很小，n 与 m最大不超过100，k不超过4，所以我们就可以直接暴力枚举所有方案。
以k = 4位例
记4个点分别为ABCD，起点为O
方案=OABCD/OACBD/OACDB...
明显方案数一共为4 * 3 * 2 * 1 = 24
对于每一种方法，我们只需要计算相邻两个顶点之间的最短距离，复杂度为O（N * M）
k = 4时最坏复杂度为O（N * M * 24）
k = 1 2 3 时复杂度明显小与O（N * M * 24）
所以做法就是直接根据k的大小，枚举所有路径上点经过的顺序，然后用bfs跑相邻两个端点的的最短路，就可以解决此问题。
京公网安备 11010502036488号