题解：CF677D Vanya and Treasure

题解基本全是根号做法，这里来个不一样的。

考虑朴素的 dp，遍历所有数字，对于每一个数字，设 $dp_{i,j}$ 表示在 $\{i,j\}$ 这个位置最少走多少步，显然当前数字的所有位置可以由上一个数字的所有位置转移过来，转移时简单的。

但这样无法通过，考虑优化，设从 $\{x_1,y_1\}$ 转移到 $\{x_2,y_2\}$，不妨设 $x_1<x_2$ 且 $y_1<y_2$，则其间的距离为 $| x_2-x_1 |+| y_2-y_1|$ 拆开即为 $x_2+y_2-x_1-y_2$，所以每次转移相当于找到前面一个数时最小的 $dp_{x_1,y_1}-x_1-y_1$ 再加上 $x_2+y_2$，把每个颜色的对应位置存下来，用二维树状数组维护即可。

这里只是从左上转移到右下的情况，需要旋转三次得到其他方向的答案。