[CF1517C]Fillomino 2

本文主要是介绍[CF1517C]Fillomino 2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

壹、题目描述 ¶

传送门 to CF

考试的时候感觉它存在贪心思路，就随便打了一个贪心填发：

考虑每个点都是从 \((x,x)\) 开始走，如果我们当前走到了 \((i,j)\)，如果能够往 \((i-1,j)\) 走，就往 \((i-1,j)\) 走，不然依次考虑 \((i,j-1),(i+1,j),(i,j+1)\) 走，直到这个数字被填完为止。

然后，它就过了......

事后看了一下 \(\rm tutorial\) 里面关于这道题的证明，它使用很巧妙的方法进行递归：

先从数字为 \(1\) 的那个格子开始，假设 \((x,x)\) 上填的数字是 \(1\)，那么它一定是自成一块。

对于 \((y,y)(y<x)\) 的格子，将 \((y+1,y)\)（就是往下走一格）和 \((y,y)\) 绑在一起，对于 \((z,z)(z>x)\) 的格子，将 \((z,z-1)\)（就是往左走一个）和 \((z,z)\) 绑在一起，然后递归处理这个问题，到最后它一定是有解的。

这篇关于[CF1517C]Fillomino 2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！