P6220 [COCI 2019/2020 #6] Skandi
题目背景
题目翻译来自 [LOJ3269](https://loj.ac/problem/3269) 。
**由于洛谷评测机原因，数据有删改。**
题目描述
**译自 [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T4.** ***[Skandi](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)***
Dragica 不仅是当地的一个半专业保龄球队的队长，还是一位充满激情的厨师。除此之外，他还是克罗地亚数一数二的填字游戏（crossword）玩家。填字游戏是一个在 $N\times M$ 的网格上游玩的游戏。在游戏开始前，部分格子已经填上了字母，作为至多两题的起点，而玩家需要根据给出的提示以水平向右或竖直向下的方向在剩下的格子填上答案。在这里，一题的答案定义为从该题起点沿提示指定方向直至网格边界或另一题起点之前的部分。如果一题的起点右边一格是空的，则该题在水平方向上存在一题；类似的，如果一题的下面一格是空的，则该题在竖直方向上存在一题。
Dragica 当然知道答案啦，但他有点鸽，想让你帮他找出完成某个填字游戏最少回答的题目数。
输入格式
无
输出格式
无
说明/提示
#### 样例 $3$ 解释：
下图展示了样例中的填词游戏，其中黑色的格子表示开始时已经填了字符的格子，在图下方所示的表中你可以看到给出的横着填和竖着填的提示。注意，已经填了字符的格子可以是零题、一题（例如第 $8$ 和 $13$ 题）或两题（例如第 $10$ 和 $12$）题的起点。要解出它，你至少需要知道 $14$ 题的答案，试试看看你会吗？~~（疑问语气）~~
*译者注：以下图片经过高清重制。中文的 crossword 没啥意义，就不翻译了。*
-----
#### 数据范围：
对于 $100\%$ 的数据，有 $2\le N,~M\le 500$。
各子任务限制见下表：
|子任务|分值|特殊限制|
|:-:|:-:|:-:|
|1|16|至多 $9$ 个格子开始前填了字符|
|2|30|$N\le 500,~M\le 10$|
|3|54|无特殊限制|