Readme

1368.Minimum-Cost-to-Make-at-Least-One-Valid-Path-in-a-Grid

解法1：BFS

如果不给修改的机会，那么我们能遍历到哪些格子？显然就是从(0,0)顺着箭头走，假设能走到Set0 = {p1,p2,...pk}这些位置。

然后考虑如果给一次修改的机会，我们能遍历到哪些格子？我们会从之前Set0集合里考察每一个格子，思考如果不按照当前的箭头走，而是可以修改成任意方向的话，下一步会到哪里？比如说p1原本的箭头指向p2，现在我们允许修改一次p1的箭头方向，那么p1可能可以走到上述集合之外的q1。同时我们顺着q1的箭头走，又可以遍历到q2,q3,q4...等一系列的位置。可见这一系列{qi}点集就是“给一次修改机会”所能到达的位置。同理，我们还可以修改p1的箭头指向r1，或者选择Set0中的其他格子修改箭头，这些操作都能得到“给一次修改机会”所能到达的位置，我们标记为Set1。

我们看出来，从Set0到Set1，就是一个BFS的过程。同理从Set1到Set2，也是BFS的过程：不断从一个集合，扩展到下一个集合，伴随step+=1.直到发现经过若干步（即修改若干次箭头）之后，就可以遍历到右下角，那么就可以返回答案。

需要注意的是，在上述过程中，从q1顺着原有的箭头扩展到q2,q3,q4...的过程也是遍历，这层遍历时的step都是保持不变的。对于这层遍历，我们也可以用dfs来实现。

解法2：Dijkstra

如果格子A的符号导向的是格子B，那么我们就认为AB之间的边权重是0；否则我们就认为AB之间的边权重是1. 于是本题就变成了求起点到终点的最短路径问题。因为图中任意两点之间的边权重不等，所以用Dijkstra是显而易见的方案。