ColorfulWolves

作者：罗哲正

关键词：最短路

题目简述

有一只狼可以把自己的颜色在$n$种颜色之间切换，每次切换需要花费一天的时间，颜色编号为$0 \sim n-1$，给定$n\times n$的由$Y$和$N$组成的字符矩阵$colormap$，$colormap[i][j]=Y$表示狼可以从颜色$i$切换到颜色$j$。 狼会按照如下方式来改变自己的颜色：每一天，如果他不能改变自己的颜色，他会保持自己的颜色不变，否则，他会变成能变成的编号最小的颜色。 第$0$天狼的颜色为$0$，他想变成颜色$n-1$，你需要通过修改$colormap$来完成这一目标，具体来说，你可以花费$1$单位代价来把某个位置的$Y$改成$N$。

求最小总花费，若无法完成目标，返回$-1$。

$2 \leq n \leq 50;colormap[i][j]='Y'or'N'.$

算法

如果$colormap$确定，显然狼之后每一天的颜色，都可以由当前颜色推出，即之后的颜色变化路径只和当前颜色有关。那么可以推出从颜色$0$变化到颜色$n-1$的路径上不存在重复的颜色，即不存在环，否则狼的颜色就会一直绕着环变化从而无法到达$n-1$。

考虑通过修改$colormap$来改变颜色的后继。对于$i,j$，如果存在$c$个$k$满足$k<j$且$colormap[i][k]=Y$，则我们需要把这些$Y$都改成$N$才可以让$j$变成$i$的后继。于是$c$就是从$i$走到$j$的花费。

接着考虑建立$n$个点表示每种颜色，按照上述方式对每个$colormap[i][j]=Y$的$(i,j)$加入权值为$c$的边，那么从$0$到$n-1$的最短路就是答案的下界。同时，由于对于每种颜色的后继修改都是独立的，而且最短路不会存在环，所以最短路是一种可行的方案。

于是我们证明了这样建图之后从$0$到$n-1$的最短路就是答案。 用Floyd求最短路就可以了。什么，你问我为什么不用dijkstra？反正有我写一个dijkstra的时间我能写三个Floyd（雾）。 时间复杂度$O(n^3)$。

总结

本题结论较为简单，但证明还需要一些微小的观察和推理，比赛时若能猜出结论可以跳过证明，在数据范围较小时最短路也可使用Floyd实现以加快解题速度。